|
|
|
ホーム
全記事一覧
|
|
|
| 今回はmemchr関数です。この関数は、nバイトの配列から文字cを探索するためのもので、文字cに一致する要素が見つかればその要素へのポインタを、見つからなければ空ポインタを返します。ここで、文字cは探索に先駆けてunsigned charに型変換されます。sが指す配列も、unsigned char型の配列であるとみなして扱われます。では、コードを見てみましょう。
#include <stddef.h>
void *memchr(const void *s, int c, size_t n)
{
register const unsigned char *ss = s;
register const unsigned char *t = ss + n;
c = (unsigned char)c;
while (ss != t && *ss != c)
++ss;
return ss != t ? (void*)ss : NULL;
}
文字が見つかればその時点のポインタを返す処理をループの中に入れると、ややコンパイル結果が煩雑になりますので、ここではループを抜けてから空ポインタにするかどうかを判別しています。
▽続きを読む▽
memchr関数をC++に対応するには、もう少し手間がかかります。というのも、C++のmemchr関数は、Cのそれとは仕様が異なるからです。C++のmemchr関数は、次の2種類が多重定義されています。
void* memchr(void* s, int c, size_t n);
const void* memchr(const void* s, int c, size_t n);
外部定義されたmemchr関数のコードはCで記述することになりますから、上記のいずれとも合致しないわけですが、C結合にしてしまえば、この程度の型の違いは無視できます。したがって、
extern "C" void* memchr(void*, int, size_t);
inline const void* memchr(const void* __s, int __c, size_t __n)
{
return memchr(const_cast<void*>(__s), __c, __n);
}
のようにすれば、C++の仕様にあわせることができます。
| | 2006/03/24 08:38｜文字列操作｜TB：0｜CM：0｜▲
|
|
| memmove関数は、memcpy関数とほとんど同じなのですが、コピー元とコピー先の領域が重なっていても構わない点が異なります。したがって、memcpyでは付けていたrestrict修飾子がmemmoveでは付きません。では、早速コードを見てみましょう。
#include <stddef.h>
void *memmove(void *s1, const void *s2, size_t n)
{
register char *ss1 = s1;
register const char *ss2 = s2;
if (n != 0)
{
if (ss1 < ss2)
{
register const char *t = ss2 + n;
do
*ss1++ = *ss2++;
while (ss2 != t);
}
else if (ss1 > ss2)
{
register const char *t = ss2;
ss1 += n;
ss2 += n;
do
*--ss1 = *--ss2;
while (ss2 != t);
}
}
return s1;
}
領域が重なっている場合、コピー先の終端部分に重なっているのか、先頭部分に重なっているのかによって、配列の最初からコピーするか最後からコピーするかを切り替えています。
配列の最後からコピーする場合（ss1 > ss2の条件）、ss1およびss2を配列の最後の要素を一つ越えたところを指すように初期化しています。そして、tはコピー元の配列の最初を指しています。これは、ポインタに整数値を加減算するとき、結果のポインタは、同じ配列内の要素を指すか、配列の最後の要素を一つ越えたところを指さなければならないからです。結果がそれらの範囲に収まらない場合、すなわちオーバーフローした場合の動作は未定義になります。
また、ss1とss2の比較ですが、ss1とss2は同じ集成体（配列または構造体）を指しているとは限らないため、厳密にいえば、この部分は未定義の動作になってしまいます。ただ、効率と可読性を考えると、他に妥当な手もないので、こうしています。コンパイル結果を調べて、期待通りに展開されていることは確認しています。
| | 2006/03/23 12:41｜文字列操作｜TB：0｜CM：4｜▲
|
|
| 前回のstrxfrm関数で使ってしまった関係上、今回は急遽memcpy関数を取り上げることにしました。こういう単純関数ほど、工夫する価値が結構あったりします。今回もアセンブリ言語を使う一歩手前まで最適化してみたいと思います。
この類の関数は、ループの中をどれだけ軽量化できるか、あるいはループの回数をどれだけ減らせるかが鍵になります。まずは素直な実装からです。
#include <string.h>
void *memcpy(void * __restrict__ s1, const void * __restrict__ s2, size_t n)
{
register char *ss1;
register const char *ss2;
for (ss1 = s1, ss2 = s2; n != 0; n--)
*ss1++ = *ss2++;
return s1;
}
やっていることはご覧の通りですので、特に説明もいらないでしょう。コンパイル結果を見てみることにしましょう。オプションは、-mh -mint32 -O2 -fomit-frame-pointerです。
_memcpy:
mov.l er4,@-er7
mov.l er0,er4
mov.l er2,er0
mov.l er4,er3
.L8:
mov.l er0,er0
beq .L7
mov.b @er1+,r2l
mov.b r2l,@er3
adds #1,er3
subs #1,er0
bra .L8
.L7:
mov.l er4,er0
mov.l @er7+,er4
rts
例によって、H8/300Hのコードであることにご注意ください。上記の.L8から.L7までがループになっています。er3がss1、er1がss2、er0がnに相当するようです。beq .L7はforの条件式の判定です。
これを踏まえた上で、もう一歩踏み込んでみます。
void *memcpy(void * __restrict__ s1, const void * __restrict__ s2, size_t n)
{
register char *ss1 = s1;
register const char *ss2 = s2;
register const char *t = ss2 + n;
while (ss2 != t)
*ss1++ = *ss2++;
return s1;
}
今度は、nをデクリメントするのではなく、終端位置を指すポインタを予め作っておいて、その値との比較を行うようにしました。同じ条件でコンパイルすると、次のようになります。
_memcpy:
mov.l er4,@-er7
mov.l er0,er4
mov.l er0,er3
mov.l er1,er0
add.l er2,er0
.L7:
cmp.l er0,er1
beq .L6
mov.b @er1+,r2l
mov.b r2l,@er3
adds #1,er3
bra .L7
.L6:
mov.l er4,er0
mov.l @er7+,er4
rts
大体同じですが、subs #1,er0の分だけ、ループの中が1行減っています。たった1命令ですが、ループの回数が増えれば、その数だけ命令数が減少することになります。さらにもう一歩踏み込みます。
void *memcpy(void * __restrict__ s1, const void * __restrict__ s2, size_t n)
{
register char *ss1 = s1;
register const char *ss2 = s2;
if (n != 0)
{
register const char *t = ss2 + n;
do
*ss1++ = *ss2++;
while (ss2 != t);
}
return s1;
}
今度はdo文を使いました。今までの二つは、ループの最初で条件判定を行っていたので、どうしてもループの中にbeq命令が入っていました。これをループの最後に判定させることで、ループの最後のbra命令をbeq命令とまとめてしまおうというのが狙いです。それでは同じ条件でのコンパイル結果です。
_memcpy:
mov.l er4,@-er7
mov.l er0,er4
mov.l er0,er3
mov.l er2,er2
beq .L2
mov.l er1,er0
add.l er2,er0
.L3:
mov.b @er1+,r2l
mov.b r2l,@er3
adds #1,er3
cmp.l er0,er1
bne .L3
.L2:
mov.l er4,er0
mov.l @er7+,er4
rts
狙い通り、ループの中はうんとシンプルになりました。
ここから先の最適化は、これまでバイト単位で書き込んでいたものをワード単位で書き込むようにすることになると思います。しかし、その方法を採用するとなると、H8/300と、H8/300HやH8Sでは別のコードを書かなければ真の最適化ができなくなります。
また、ワード単位の書き込みの場合、最初に境界調整を調べたりする処理が入るので、サイズが小さい場合はかえって効率が低下します。この辺りの落としどころも難しいので、今回はこの程度にしておきたいと思います。
アセンブリ言語を使う場合は、H8にはEEPROM命令というブロック転送の命令があるので、それを使うのがよさそうです。この話は、いずれ機会を改めてできたらと思います。
| | 2006/03/15 02:27｜文字列操作｜TB：0｜CM：0｜▲
|
|
| <string.h>には、strcoll関数の他にもうひとつロケールに依存する関数が宣言されます。それが、strxfrm関数です。この関数は何をするかというと、ナル終端文字列をロケールに応じて変換し、strcmp関数で単純比較すれば、元の文字列を直接strcoll関数で比較したのと同じ結果になるようにするものです。
strxfrm関数はsize_t型の返却値を返しますが、この値は変換後の文字列の長さを意味します。変換用のバッファが足りなくても、変換後の長さを返しますので、いったん必要な配列のサイズを調べてから、改めて変換するような使い方もできます。
strcoll関数もそうであったように、とりあえずは"C"ロケールしか扱いませんので、今回は暫定実装のみにしておきます。
#include <string.h>
size_t strxfrm(char * __restrict__ s1, const char * __restrict__ s2, size_t n)
{
size_t result = strlen(s2);
if (n != 0) {
if (result < n)
strcpy(s1, s2);
}
return result;
}
strncpy関数ではなく、長さを調べてからstrcpy関数を使っているのは、strncpy関数は配列のサイズ一杯までナル文字を埋める仕様になっていますが、strxfrm関数は最初のナル文字以降に書き込んではいけないからです。
ナル文字を書き込んでいない不具合があったので、修正しました。
それはそうと、memcpy関数はまだ取り上げていませんでした。順序がバラバラですが、次回はmemcpy関数を取り上げたいと思います。
最初はmemcpyを使っていましたが、不具合を修正しているうちに、memcpyがなくなってしまいました。
| | 2006/03/15 00:38｜文字列操作｜TB：0｜CM：4｜▲
|
|
| strcmp関数はナル終端文字列を単純比較するための関数でしたが、strcoll関数はLC_COLLATEカテゴリのロケールに基づく比較を行います。具体的な比較方法は完全にライブラリの実装依存になるわけですが、抑えるべきポイントは、ロケールの設定で扱う文字コードを変更しても、順序が保たれるようにすることと、ワイド文字列用のwcscoll関数と整合性を持たせられるようにすることかと思います。
といっても、現時点ではとりあえず"C"ロケールしか考慮しないことにしていますので、小難しい実装は先送りにして、とりあえずは形式的な実装のみで済ませることにします。"C"ロケールの場合には、strcmp関数と全く同じ動作で構いません。
#include <string.h>
int strcoll(const char *s1, const char *s2)
{
return strcmp(s1, s2);
}
効率を考えればインライン関数にするのもよいでしょうが、そもそも高速に比較したいのであれば、strcoll関数を使うこと自体が間違っているのと、いずれはロケールに対応したいということもあるので、この程度にしておきます。
| | 2006/03/14 01:41｜文字列操作｜TB：0｜CM：0｜▲
|
|
| 本サイトで取り上げている標準Cライブラリは、TOPPERS/JSPカーネル上で動作させることを目指していますが、このたび、JSPカーネルの理解の助ける意味で、新サイト「TOPPERS/JSPカーネル ドキュメント」を公開することにしました。
現状では、Doxygenで自動生成したページしかありませんが、必要に応じて補足説明を加筆していければと考えております。本サイト同様、よろしくお願いいたします。
| | 2006/03/10 21:02｜開発環境｜TB：0｜CM：0｜▲
|
|
| 標準Cライブラリには文字列を比較するための関数がいくつか用意されていますが、今回はナル終端文字列を単純比較するためのstrcmp関数を取り上げます。
strcmp関数は、二つの文字列を先頭から順に比較し、文字が異なるか、ナル文字に達した時点で比較を終えます。そして、最後の文字どうしを比べて、第1引数の方が大きければ正の値を、第2引数の方が大きければ負の値を、等しければ0を返します。
このように単純な仕様の関数ですが、一点だけ注意すべきなのは、文字の比較は、unsigned char型として行わなければならない点です。これらを踏まえると、実装は次のようになります。
#include <stddef.h>
int strcmp(const char *s1, const char *s2)
{
register const unsigned char *ss1, *ss2;
for (ss1 = (const unsigned char*)s1, ss2 = (const unsigned char*)s2;
*ss1 == *ss2 && *ss1 != '\0';
ss1++, ss2++)
;
return *ss1 - *ss2;
}
strcpy関数やstrlen関数と比べるとやや煩雑になりましたが、それでもこの程度です。
| | 2006/03/03 20:46｜文字列操作｜TB：0｜CM：0｜▲
|
| |
|
|
ホーム
全記事一覧
|
|
|
