C99に対応した標準Cライブラリの実装レポートを行っていきます。

プロフィール 

高木信尚

Author:高木信尚

ホームページ
ブログ

最近の記事 

最近のコメント 

最近のトラックバック 

月別アーカイブ 

カテゴリー 

ブロとも申請フォーム 

この人とブロともになる

ホーム 全記事一覧

 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
--/--/-- --:--|スポンサー広告

 

文字列の連結を行うstrcat関数は、strlen関数とstrcpy関数を合わせたような機能を持っています。つまり意味的には、

char *strcat(char * restrict s1, const char * restrict s2)
{
  strcpy(s1 + strlen(s1), s2);
  return s1;   // 間違っていたので少し直しました
}

ということになるわけです。実装もこれと大差はありませんが、strlenやstrcpyといった関数を呼び出すのではなく、直接展開しているだけです。したがって、

#include <stddef.h>

char *strcat(char * __restrict__ s1, const char * __restrict__ s2)
{
  register char *ss;
  for (ss = s1; *ss != '\0'; ss++)
    ;
  for (; (*ss = *s2) != '\0'; ss++, s2++)
    ;
 return s1;
}

とすれば完成です。

ところで、strcat という関数名ですが、STRing ConcAtenaTe の意味だとか。かなり無理があるような気がするのは私だけでしょうか。
スポンサーサイト
2006/02/27 22:17|文字列操作TB:0CM:0

 

今回はstrcpy関数の実装についてです。この関数は非常に単純な上に、実装上の選択肢もほとんどないのでさらっと流します。

#include <stddef.h>

char *strcpy(char * __restrict__ s1, const char * __restrict__ s2)
{
  for (register char *ss = s1; (*ss = *s2) != '\0'; ss++, s2++)
    ;
  return s1;
}

コメントすべき点としては、引数に__restrict__が付いていることぐらいでしょうか?s1とs2が指す領域が重複しているとダメですので、重複がないことを明示的に指定する型修飾子__restrict__を付けています。

restrictではなく、__restrict__にしているのは、C99以外でも使えるようにするためです。もっとも、ヘッダはともかく、関数定義ではrestrictを使っても問題ないのでしょうが、一応関数原型にあわせておくことにします。

あと、forの「節1」はC99からは宣言も許されるようになりました。この「標準Cライブラリの実装」では、C99の新文法も積極的に取り入れていきたいと思います。

ところで、forの「節1」に宣言が使えるようになったので、C++と同じになったかと思うとそうでもないようです。forの繰返し条件である「式2」は、あくまでも「式」であり、ここで宣言を行うことはできません。C++なら、次のような書き方ができるのですが...

for (char *ss = s1; char c = (*ss = *s2); ss++, s2++)

この辺りは結構罠にはまりそうですね。
2006/02/24 01:20|文字列操作TB:0CM:0

 

今回は文字列の長さを調べるstrlen関数です。こういう単純な関数は、アセンブリ言語で記述すれば、より高速化できる場合もあるのですが、とりあえずはC言語で実装することにします。アセンブリ言語を使って、高速化の余地があるものについては、後ほど機会があれば扱いたいと思います。

それでは早速strlenの実装を行います。まずは、最も素直な実装からはじめてみましょう。

#include <stddef.h>

size_t strlen(const char *s)
{
  size_t n;
  for (n = 0; *s != '\0'; s++, n++)
    ;
  return n;
}

ご覧の通り、文字列sを最初から順番に調べ、ナル文字が見つかるまでnをインクリメントしています。この実装でも動作はしますが、あまり効率はよくありません。なぜなら、1回ループするごとに、2回もインクリメントを行っているからです。

ループの中はできる限り単純にし、1回あたりの処理を少なくした方が高速になります。したがって、

#include <stddef.h>

size_t strlen(const char *s)
{
  register const char* ss;
  for (ss = s; *ss != '\0'; ss++)
    ;
  return ss - s;
}

とすれば、ループ1回あたりのインクリメントは1回になります。ssをregister記憶クラスにしているのはお呪いのようなようなものですが、レジスタに割り付けられることを期待しているのは事実です。

このコードを、-mh -O2 -fomit-frame-pointerオプションを付けてコンパイルした結果は次の通りです。

_strlen:
    mov.l   er0,er3
    mov.b   @er3,r2l
.L8:
    mov.b   r2l,r2l
    beq .L7
    adds    #1,er0
    mov.b   @er0,r2l
    bra .L8
.L7:
    sub.l   er3,er0
    rts

ターゲットがH8/300Hであることにご注意ください。H8のアセンブラに慣れていない方でも、何らかのアセンブリ言語の経験があれば、大筋で理解できるかと思います。er0とかer3というのは32ビットのレジスタです。r2lというは、32ビットレジスタer2の下位8ビットです。

つまり、引数のsがer0に、一時変数のssがer3に割り付けられていることが分かります。r2lは*ssを読み込んでナル文字と比較するために使われています。どうやら期待通りの結果になったようです。

アセンブリ言語で直接記述すれば、もう少し効率を上げることができそうですが、最初にお断りした通り、今は触れないことにしておきます。
2006/02/19 23:52|文字列操作TB:0CM:0

 

今回から<string.h>で宣言される関数についてお話していきます。まずは、後回しにしていると忘れてしまいそうな、strerror関数からです。strerror関数の使用頻度は必ずしも高くないので、これまで使ったことがない方もおられると思います。そこで、簡単にこの関数について解説しておきます。

strerror関数は、errno に設定するエラー番号を引数として渡すことで、そのエラー番号に応じた文字列を返す関数です。例えば、EDOMを渡せば、"Domain error"という文字列を返すわけです。具体的にどんな文字列を返すかは、処理系に依存します。

それでは実際の実装に入ります。

#include <errno.h>

char *strerror(int errnum)
{
  char *result;
  switch (errnum)
  {
  case 0:
    result = "No error";
    break;
  case EDOM:
    result = "Domain error";
    break;
  case ERANGE:
    result = "Range error";
    break;
  case EILSEQ:
    result = "Illegal sequence";
    break;
  default:
    result = "Unknown error";
    break;
  }
  return result;
}

今回の実装では、エラー番号は三種類しかないのでswitch文にしましたが、エラー番号が多い場合は表引きの方がよさそうです。また、文字列定数を(const修飾がない)char*で返しているところも、いまひとつ安全性に欠けますが、これは標準Cの仕様なので致し方ありません。

2006/02/15 23:01|文字列操作TB:0CM:0

 

今回から、<string.h>ヘッダと、その中で宣言されている関数についてお話していきます。<string.h>の内容は、C89以来ほとんどかわっていないのですが、C99からは、restrict修飾子が加わったことで若干関数原型が変わっています。

まず、<string.h>ヘッダにも、<stddef.h>ヘッダと同様、NULLマクロとsize_t型の定義があります。これについては、<stddef.h>の回で解説済みですので、そちらを参照してください。

restrict修飾子についてですが、このキーワードをそのまま使うと、C99のときはよいのですが、C95以前のバージョンやC++などで問題が発生します。したがって、restrictではなく、GNU拡張である__restrict__を用いて実装していくことにします。

個々の関数に関しては、次回以降にお話します。
2006/02/13 00:46|文字列操作TB:0CM:0

 

<ctype.h>のところで、書くべきことは書いてしまったので、おさらいになりますが、一応to~系の関数についても触れておきます。

通常、to~系関数は、

int tolower(int c)
{
  return isupper(c) ? c - 'A' + 'a' : c;
}

のように実装されるのですが、この方法には問題があります。英文字の連続性については、文字コードを特定することで回避できますが、"C"ロケール以外をにらんだ場合、例えばドイツ語のß(エスツェット)は小文字しかないため、対応する大文字が存在しません。日本語の半角カナも類似の問題があります。

そこで、to~関数も表引きの手法をとることにします。to~系関数はEOFを受け入れる必要はないのですが、念のためis~系関数と同様に、-1~255までの257要素の配列にしたいと思います。

/* tolower.c */
const unsigned char __tolower_C[257] = { ... };
const unsigned char *__tolower = __tolower_C + 1;

/* toupper.c */
const unsigned char __toupper_C[257] = { ... };
const unsigned char *__toupper = __tolower_C + 1;

ヘッダ側は、

#ifdef __cplusplus
extern "C" {
#endif

extern const unsigned char __tolower_C[];
extern const unsigned char __toupper_C[];

extern const unsigned char *__tolower;
extern const unsigned char *__toupper;

#ifdef __cplusplus
}
#endif

とします。そして、各関数はインライン関数として、

static __inline__ int tolower(int c)
{
#ifdef __ONLY_C_LOCALE
  return isupper(c) ? c - 'A' + 'a' : c;
#else
  return __tolower[c];
#endif
}

static __inline__ int toupper(int c)
{
#ifdef __ONLY_C_LOCALE
  return islower(c) ? c - 'a' + 'A' : c;
#else
  return __toupper[c];
#endif
}

と定義することができます。
もちろん、各関数は外部関数としても同様の定義が必要になります。
2006/02/11 02:03|文字種別TB:0CM:0

 

今回は空白類文字の判別関数についてお話します。これで<ctype.h>内で宣言されるis~系関数は終わりです。

isspace関数の厳密な仕様は、isalnum関数が偽となる処理系定義の文字、または標準空白類文字に対して真となります。標準空白類文字は、空白類文字とは異なり、復帰文字 '\r' が含まれます。isspace関数の実装は、他のis~関数と同様、

static __inline__ int isspace(int c)
{
  return __ctype[c] & _SPACE;
}

とします。"C"ロケールで真になるのは、空白文字 ' '、水平タブ文字 '\t'、垂直タブ文字 '\v'、書式送り文字 '\f'、改行文字 '\n'、および復帰文字 '\r' です。

さて、C95までであれば、ここまででis~系関数は終わりなのですが、C99では関数が一つ追加されました。それがisblank関数です。この関数は行内空白類文字を判別するためのものです。"C"ロケールでは、標準行内空白類文字かどうかの判別を行うことになります。標準行ない空白類文字には、空白文字 ' ' と水平タブ '\t' が含まれます。

厳密に言えば、isblank関数もロケールによって動作が変わるので、表引きにすべきなのかもしれませんが、実際問題として、およそ扱う可能性のあるロケールでは、標準行内空白類文字の判別ができれば十分ですので、今回は決めうちにします。

というのも、C95の範囲の関数で、8ビットあるビットパターンはすべてふさがっており、isblank関数を表引きにしようとすると、それだけで表のサイズが倍になってしまうからです。したがって、今回は、

static __inline__ int isblank(int c)
{
  return c == ' ' || c == '\t';
}

のように定義することにします。
2006/02/08 23:59|文字種別TB:0CM:0

 

<ctype.h>内で宣言される関数についての話が続いていますが、今回は制御文字の判別です。"C"ロケールでは、最低限サポートしなければならない制御文字は、逆斜線+英一文字で表現できる文字だけでよいのですが、ASCII、というかISO-646およびその上位互換の文字コードの場合、0x00~0x1fおよび0x7fを制御文字として扱いますので、今回もそれにあわせることにします。

したがって、

static __inline__ int iscntrl(int c)
{
  return 0x00 <= c && c <= 0x1f || c == 0x7f;
}

のように記述してもよいのですが、とりあえずは表引きを使って、

static __inline__ int iscntrl(int c)
{
  return __ctype[c] & _CNTRL;
}

とすることにします。
2006/02/08 23:44|文字種別TB:0CM:0

 

前回に引き続き、<ctype.h>内で宣言される関数の実装についてのお話です。前回は英数字の判別についてでしたので、今回はそれ以外の表示文字についてです。それ以外の表示文字というのは、具体的には、区切り文字と空白文字があります。早速コードを見てみましょう。

static __inline__ int ispunct(int c)
{
  return __ctype[c] & _PUNCT;
}

上記は、区切り文字の判別を行う関数です。区切り文字と英数字を含めた、表示文字かどうかの判別は次の関数で行います。

static __inline__ int isgraph(int c)
{
  return __ctype[c] & (_LOWER|_UPPER|_DIGIT|_PUNCT);
}

isgraph関数では、空白 ' ' は偽の扱いになります。空白 ' ' まで含めた表示文字の判別は、次の関数で行います。

static __inline__ int isprint(int c)
{
  return __ctype[c] & (_LOWER|_UPPER|_DIGIT|_PUNCT|_BLANK);
}

これらの関数を用いることで、表示文字、あるいは印字可能な文字かどうかの判別を行うことができます。

前回取り上げた関数同様、これらの関数も外部定義が必要になります。今後も、特に触れない限り、ヘッダ内でインライン関数として定義した関数は、別途外部関数を定義する必要が発生します。
2006/02/08 01:03|文字種別TB:0CM:0

 

今回から数回にわたって、<ctype.h>の中で宣言される関数の具体的な実装についてお話します。まずは、英数字の判別を行う関数群です。この中には、isalnum, isalpha, isdigit, islower, isupper, およびisxdigit関数が含まれます。

まず、効率を考えて、これらの関数はヘッダ内でインライン関数として実装することを考えます。このとき、C99ではinlineがサポートされますが、C89等での使用も考慮に入れ、GNU拡張である__inline__キーワードを使用することにします。これは、localeconv関数の実装でも利用した方法です。

static __inline__ int isalnum(int c)
{
  return __ctype[c] & (_LOWER|_UPPER|_DIGIT);
}

このように、前回定義した_LOWER等を用いて、表中の値のビットパターンを調べることで文字種別の判別を行います。is~系関数は、真のときには非0を返せばよいので、必ずしも1ではない値が返却値になりますが、これに関しては問題ないでしょう。

以下、同様に、

static __inline__ int isalpha(int c)
{
  return __ctype[c] & (_LOWER|_UPPER);
}
static __inline__ int isdigit(int c)
{
  return __ctype[c] & _DIGIT;
}
static __inline__ int islower(int c)
{
  return __ctype[c] & _LOWER;
}
static __inline__ int isupper(int c)
{
  return __ctype[c] & _UPPER;
}
static __inline__ int isxdigit(int c)
{
  return __ctype[c] & _XDIGIT;
}

のように記述することが可能です。

さて、インライン関数に関してはこれでよいのですが、<ctype.h>をインクルードせず、ユーザーが自分で関数原型を記述して、これらの関数を呼び出した場合でも正しく動作する必要があります。これを実現するには、インライン関数と同等の定義を外部関数として行う必要があります。

ライブラリが提供する外部関数は、極力、一関数につき一翻訳単位とする方が望ましいでしょう。アプリケーションであれば、これらの関連性のある関数は、一つのソースコードに列記したくなるところですが、ライブラリでそのようなことをすると、不必要な関数までリンクされる結果となり、空間効率が悪くなります。
2006/02/08 00:54|文字種別TB:0CM:0

 

今回は文字種別の判別と変換のためのヘッダである<ctype.h>についてお話します。<ctype.h>で宣言される関数は、"C"ロケールに限定すれば非常に単純なものばかりです。今回は、とりあえずは"C"ロケールにしか対応しませんが、他のロケールへの拡張性も視野に入れていますので、ちょっと複雑になります。

まずはis~系関数の実装方法について考えてみましょう。実装方法はいくつか考えられますが、ロケールの切り替えが簡単なことや、実行効率のことを考えて、表引きを採用したいと思います。この方法は、多くの標準Cライブラリで採用されている最も一般的な方法です。

表引きは、is~系関数の引数が取りうる値ごとに、文字種別を表すビットパターンの配列を参照することで行います。文字種別を表すビットパターンは、下記のように、

#define _CNTRL 0x01
#define _LOWER 0x02
#define _UPPER 0x04
#define _DIGIT 0x08
#define _PUNCT 0x10
#define _SPACE 0x20
#define _BLANK 0x40
#define _XDIGIT 0x80

といった、文字種別の基本要素ごとにビットを割り当ててやれば、8ビットで済みます。すなわち、unsigned char型の配列にできるので、非常に効率のよい実装が可能になります。ここで、_BLANKは空白 ' ' を表すものであって、isblank関数が真を返すものではありません。

表引き用の配列は、添え字として-1~255を使えるようにしなければなりません。-1はEOFに、255はUCHAR_MAXに相当します。このため、257要素の配列を作成して、参照する時点で1ずらすようにします。

const unsigned char __ctype_C[257] = { ... };
const unsigned char *__ctype = __ctype_C + 1;

char型が符号付きの場合、負の値をそのまま配列の添え字にすると問題が発生します。しかし、is~系関数の引数は、EOFまたは0~UCHAR_MAXでなければならず、それ以外の値を与えると規格上も未定義なので、今回は放置します。これは、安全対策のために余計なことをすると、オーバーヘッドが非常に大きいためです。

ヘッダ側では、配列およびいったんそれを受けるポインタ変数を以下のように宣言します。

#ifdef __cplusplus
extern "C" {
#endif
extern const unsigned char __ctype_C[];
extern const unsigned char *__ctype;
#ifdef __cplusplus
}
#endif

#ifdef __ONLY_C_LOCALE
#define __ctype (__ctype_C+1)
#endif

このようにしておくことで、is~系関数をインライン関数として実装することも簡単になります。

<ctype.h>には、is~系関数のほかにto~系関数も含まれています。通常、to~系関数は、

int tolower(int c)
{
  return isupper(c) ? c - 'A' + 'a' : c;
}

のように実装されるのですが、この方法には問題があります。英文字の連続性については、文字コードを特定することで回避できますが、"C"ロケール以外をにらんだ場合、例えばドイツ語のß(エスツェット)は小文字しかないため、対応する大文字が存在しません。日本語の半角カナも類似の問題があります。

そこで、to~関数も表引きの手法をとることにします。to~系関数はEOFを受け入れる必要はないのですが、念のためis~系関数と同様に、-1~255までの257要素の配列にしたいと思います。

const unsigned char __tolower_C[257] = { ... };
const unsigned char *__tolower = __tolower_C + 1;

ヘッダ側は、
#ifdef __cplusplus
extern "C" {
#endif
extern const unsigned char __tolower_C[];
extern const unsigned char *__tolower;
#ifdef __cplusplus
}
#endif

__ONLY_C_LOCALEが定義されている場合には、表引きではなく、先述したように、文字判別を行った上で、計算による変換を行う方がよいでしょう。また、上記ではtolower関数だけを取り上げましたが、toupper関数についても同様です。

<ctype.h>で宣言される各関数の詳細については、次回以降にお話します。


▽続きを読む▽
2006/02/07 10:34|文字種別TB:0CM:0

 

<locale.h>で宣言される関数のうち、もう一つはsetlocaleです。この関数は、特定のカテゴリを指定したロケールに設定します。何度も書いてきましたが、とりあえずは"C"ロケールだけを実装しますので、今回は"C"ロケールにのみ対応したsetlocaleを扱うことにします。""を指定した場合も"C"ロケールになります。

#include <locale.h>

char *setlocale(int category, const char *locale)
{
  char *result = NULL;

  if (0 <= category && category <= 5)
  {
    if (locale == NULL)
    {
      result = "C";
    }
    else
    {
      if (*locale == 'C')
        ++locale;
      if (*locale == '\0')
      {
        __lconv = &__lconv_C;
        result = "C";
      }
    }
  }
  return result;
}

"C"ロケール以外に対応させるには、おそらく全面的な書き直しになりますが、当面これで済ませたいと思います。
2006/02/02 00:48|文化圏固有動作TB:0CM:0

ホーム 全記事一覧

ブログ内検索 

お勧め書籍 

RSSフィード 

リンク 

このブログをリンクに追加する

Copyright(C) 2006 TAKAGI Nobuhisa All rights reserved.
Powered by FC2ブログ. template designed by 遥かなるわらしべ長者への挑戦.
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。