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

プロフィール　

Author:高木信尚

ホームページ
 ブログ

最近のコメント　

最近のトラックバック　

月別アーカイブ　

カテゴリー　

ブロとも申請フォーム　

この人とブロともになる

ホーム全記事一覧 << 前ページ次ページ >>

2008/10/07 11:43｜｜▲

<string.h>ヘッダで宣言されている探索系の関数は、似通ったものも少なくないのですが、このstrpbrk関数も、そんな探索系の関数のひとつです。

前回のstrstr関数と同様、どうすれば最も効率がよくなるのか、いまいちよくわからないのですが、とりあえず今回は深く考えずに素直に作ってみました。


#include <stddef.h>

char *strpbrk(const char *s1, const char *s2)
{
  if (*s2 != '\0') {
    for (register int c; (c = *s1) != '\0'; s1++)
      for (register const char *ss = s2; *ss != '\0'; ss++)
        if (c == *ss)
          return (char*)s1;
  }
  return NULL;
}

ほとんど何の捻りもありません。

探索系の関数は、他にstrcspn関数とstrspn関数がありますが、慣れないと、どれがどんな機能だったか非常に紛らわしいですね。

▽続きを読む▽

2006/04/30 19:59｜文字列操作｜TB：0｜CM：0｜▲

strchr関数は、文字列の中から指定した「文字」を探す関数でしたが、strstr関数は指定した「部分文字列」を探す関数です。意味的にはよく似ているのですが、細部の仕様がいろいろ異なっていたりします。

今回は、どのように実装すれば最も効率がよくなるのか、いろいろ検討したのですが、結局力任せで探索する方法を選んでしまいました。一応、検討した内容を簡単に書いておきます。

strstr関数は、数kバイトもある文字列を扱うことは稀なので、あまり凝ったアルゴリズムを使うと、短い文字列ではかえって速度が低下します。そこで、2～4文字をワード単位で比較する方法も考えたのですが、場合分けが複雑になり、あまり有効ではないと判断しました。

結局出来上がったコードは、いまいちパッとしませんが、次のようになりました。


#include <stddef.h>

char *strstr(const char *s1, const char *s2)
{
  int c = *s2++;
  if (c == '\0')
    return (char*)s1;
  do 
    if (*s1 == c) {
      register const char *ss1, *ss2;
      for (ss1 = s1 + 1, ss2 = s2;
           *ss2 != '\0' && *ss1 == *ss2;
           ss1++, ss2++)
        ;
      if (*ss2 == '\0')
        return (char*)s1;
    }
  while (*s1++ != '\0'); 
  return NULL;
}

この辺の関数になってくると、次第に関数の出口（return文）が増えてきます。一箇所にまとめるのは簡単ですが、ブロックの入れ子が深くなるのと、若干無駄なコードが入るので、あえてこのようにしています。

▽続きを読む▽

strstr関数も、C++では、次の2つの形式が多重定義されます。


char* strstr(char* s1, const char* s2);
const char* strstr(const char* s1, const char* s2);

これらの対応は、strchr関数などと同じなので、詳細は割愛します。

2006/04/20 11:45｜文字列操作｜TB：0｜CM：0｜▲

strrchr関数は、strchr関数と似ていますが、指定した文字が最後に現れた位置を返します。逆方向に探索を行ってもよいのですが、それでは、少なくとも文字列を2回走査しないといけないので、順方向に探索し、指定した文字が現れた時点で変数を上書きしていく方法を採ります。


#include <stddef.h>

char *strrchr(const char *s, int c)
{
  char *result = NULL;
  c = (char)c;
  do
    if (*s == c)
      result = (char*)s;
  while (*s++ != '\0');
  return result;
}

ほとんどstrchr関数と変わりませんが、文字が見つかった時点で即終了するのではなく、いったんresultに格納して、ループを続行しています。

▽続きを読む▽

strrchr関数は、strchr関数と同様、C++では以下の2種類の形式が多重定義されています。


char* strrchr(char* s, int c);
const char* strrchr(const char* s, int c);

外部定義されたstrrchr関数のコードはCで記述することになりますから、上記のいずれとも合致しないわけですが、C結合にしてしまえば、この程度の型の違いは無視できます（この辺りの事情はstrchr関数と同じです）。したがって、


extern "C" char* strrchr(char*, int);

inline const char* strrchr(const char* __s, int __c)
{
  return strrchr(const_cast(__s), __c);
}

とすればOKです。

2006/04/14 00:40｜文字列操作｜TB：0｜CM：0｜▲

strchr関数は、文字列の中から指定した文字を見つけるための関数です。memchr関数とも似ていますが、ナル文字が現れるまで探索を続けるか、予め長さを指定しているかの違いがあります。機能的にはよく似ていても、探索の終了条件が異なるとコードはかなり違ってきます。


#include <stddef.h>

char *strchr(const char *s, int c)
{
  c = (char)c;
  do
    if (*s == c)
      return (char*)s;
  while (*s++ != '\0');
  return NULL;
}

ここで、最初の行でcをchar型にキャストしていますが、これは元のcがCHAR_MIN～CHAR_MAXの範囲に収まっているかどうかわからないためです。charが符号付きの場合、このようなキャストは処理系定義の動作になりますが、GCCでは期待通りの結果になるため、この際移植性は捨てて、このような書き方にしました。

▽続きを読む▽

strchr関数は、memchr関数と同様、C++では以下の2種類の形式が多重定義されています。


char* strchr(char* s, int c);
const char* strchr(const char* s, int c);

外部定義されたstrchr関数のコードはCで記述することになりますから、上記のいずれとも合致しないわけですが、C結合にしてしまえば、この程度の型の違いは無視できます（この辺りの事情はmemchr関数と同じです）。したがって、


extern "C" char* strchr(char*, int);

inline const char* strchr(const char* __s, int __c)
{
  return strchr(const_cast(__s), __c);
}

とすればOKです。

2006/04/13 10:16｜文字列操作｜TB：0｜CM：2｜▲

memset関数は、メモリブロック中の全バイトを指定した文字で埋めます。単純な関数ですが、結構奥が深く、最適化の余地もかなりあります。ところが、いろいろ実験してみたところ、C言語レベルでの最適化は限界があり、あまりよい結果が得られません。

memset関数の最適化は、メモリブロックへの書き込みを、可能な限りワード単位で行うようにするものですが、memset関数の使用頻度が最も高いのは、構造体のゼロ初期化である可能性が高く、それほど大きなメモリブロックを扱わないのであれば、いっそバイト単位で操作した方が、無駄が少なく、効率が上がる可能性もあります。

とりあえず、ワード単位で書き込むコードを挙げます。

#include <stddef.h>
#include <stdint.h>

void *memset(void *s, int c, size_t n) 
{
  if (n != 0)
  {
    register uintptr_t addr = (uintptr_t)s;
    register uintptr_t t = addr + n;
    if (((addr | n) & 1) == 0) {
      for (unsigned int val = (uint8_t)c | (uint8_t)c << 8;
           addr < t;
           addr += sizeof(uint16_t)) {
        *(uint16_t*)addr = val;
      }
    }
    for (; addr < t; ++addr)
      *(uint8_t*)addr = c;
  }
  return s;
}

上のコードを-mh -mint32 -O2 -fomit-frame-pointerオプションを指定してコンパイルすると、次のようになります。

_memset:
    mov.l   er4,@-er7
    mov.l   er5,@-er7
    mov.l   er6,@-er7
    mov.l   er0,er4
    mov.l   er1,er5
    mov.l   er2,er2
    beq .L2
    mov.l   er0,er3
    add.l   er2,er0
    or.l    er4,er2
    btst    #0,r2l
    bne .L3
    sub.l   er2,er2
    mov.b   r1l,r2l
    mov.l   er2,er1
    mov.w   e1,r6
    mov.b   r6l,r6h
    mov.b   r1h,r6l
    mov.b   r1l,r1h
    sub.b   r1l,r1l
    mov.w   r6,e1
    or.l    er2,er1
    cmp.l   er0,er4
    bhs .L3
.L7:
    mov.w   r1,@er3
    adds    #2,er3
    cmp.l   er0,er3
    blo .L7
.L3:
    cmp.l   er0,er3
    bhs .L2
    mov.b   r5l,@er3
    adds    #1,er3
    bra .L3
.L2:
    mov.l   er4,er0
    mov.l   @er7+,er6
    mov.l   @er7+,er5
    mov.l   @er7+,er4
    rts

内部的に使用しているレジスタが多く、そのためにer4, er5, er6の3つのレジスタを退避しなければならず、あまり好ましい結果になりませんでした。

現状では、メモリブロックへの書き込みを順方向（アドレスの小さい方から大きい方）に行っていますが、これを逆方向に行うようにすれば、変数 t が不要になるため、若干なしになる気もしますが、とりあえず、現時点ではこのままにしておき、アセンブリ言語で記述しなおす際に再検討したいと思います。