トップ > C > uint8とかMiniseのコード読んだりとか

uint8とかMiniseのコード読んだりとか

C C++

Miniseのコード読みの続き。uint8とかuint64とか出てきてなんじゃいなという感じだったので調べてみる。

Minise::addFile

http://developers.curlap.com/curl/docs/rte/6.0/ja/docs/ja/dguide/primitive.htmlによると

データ型 説明 既定値 サイズ(ビット) 有効範囲
int 32ビット符号付き整数 0 32 -2,147,483,648 〜 2,147,483,647
int8 8ビット符号付き整数 0 8 -128 〜 127
int16 16ビット符号付き整数 0 16 -32,768 〜 32,767
int32 32ビット符号付き整数 0 32 -2,147,483,648 〜 2,147,483,647
int64 64ビット符号付き整数 0 64 -9,223,372,036,854,775,808 〜 9,223,372,036,854,775,807
uint 32ビット符号なし整数 0 32 0 〜 4,294,967,295
uint8 8ビット符号なし整数 0 8 0 〜 255
uint16 16ビット符号なし整数 0 16 0 〜 65,535
uint32 32ビット符号なし整数 0 32 0 〜 4,294,967,295
uint64 64ビット符号なし整数 0 64 0 〜 18,446,744,073,709,551,615
byte 8ビット符号なし整数 0 8 0 〜 255

ということらしい。

そもそもMiniseの中の文字列がどう扱われているかを見てみる。

int Minise::addFile(const char* fileName){
 FILE* fp = fopen(fileName, "rb");
  if (fp == NULL){
    what_ << "cannot open " << fileName;
    return -1;
  }
  
  fseek(fp, 0, SEEK_END);
  size_t fileSize = ftell(fp);
  rewind(fp);
  
  vector<uint8_t> content(fileSize);
  
  size_t readSize = fread(&content[0], sizeof(uint8_t), fileSize, fp);
  if (readSize != fileSize){
    what_ << "read error readSize:" << readSize << " fileSize:" << fileSize;
    fclose(fp);
    return -1;
  }

  addDoc(fileName, content);
  fclose(fp);
  return 0;
}

std::stringとかに保存してるんじゃなくて、uint8_tのvectorに保存している。std::stringはstd::vectorのようなもので、charは(unsignなら)0から255が有向範囲だと考えるとstd::vectorとstd::vectorは実質同じもの...でいいのだろうか。よく分からない。<追記>
Twitterで教えていただいたので、追記。/usr/include/stdint.hにuint8_tとかは定義されているらしく(組み込みの型みたいなのだと思ってた、、、)、自分の環境だと

#ifndef _UINT8_T
#define _UINT8_T
typedef unsigned char         uint8_t;
#endif /*_UINT8_T */

と書かれていた。ということで上の疑問は「std::vectorとstd::vectorなら完全に同じ」がfinal answerということになりそうだ。

C++はちょっとやってるけど、Cはほとんど知らないも同然なのでいくつか知らない関数が出てきた(ゆとりです)。

  • fseek
    • int fseek(FILE *stream, long offset, int whence);となっていて、whenceを基準にoffsetバイト移動する
    • Miniseの場合は、fseek(fp, 0, SEEK_END);となっていて最後のところに移動している
  • ftell
    • long ftell(FILE *stream);となっていて、現在地を数値で返す関数
    • Miniseだとsize_t fileSize = ftell(fp);となっていて、あとでuint8_tのvectorにつめこみたいので、サイズが必要な感じ
  • rewindはvoid rewind(FILE *stream);となっていて、ファイルの読み込み位置を先頭に戻す
    • Miniseはここまでファイルからデータを読んではいないことに注意

どうでもいいけど、初めてman fseekとかやった(ぇ。vector content(fileSize);となっているけど、サイズが分かっているなら最初に指定したほうがpush_backしたりするとき(ここではfreadだから違うけど)に効率がいいものなのかなという疑問が湧いたのでちょっと調べてみた。

Effective STL―STLを効果的に使いこなす50の鉄則の第14項付近を見ると、「要素の挿入が必要であり、コンテナの容量が不足しているときは、再割り当てが常に発生する。したがって、再割り当てを避けるためには、reserveを使い、できるだけ早く(コンテナの作成直後が理想的)、コンテナの容量を十分な大きさに設定することが必要である」とあった。この場合はまさにコンテナの作成直後のケースに該当するのかな。ちなみに再割り当てとは

  • 生のメモリの割り当てと割り当て解除
  • オブジェクトのコピーと破棄
  • 反復子、ポインタ、参照の無効化

などから構成される、とあった。

Minise::parseUTF8

他にもスペース区切りで単語を分けるparseSeparatedとかっていう関数もあるけど、ここではMinise::parseUTF8のほうを見てみる。

int Minise::parseUTF8(const vector<uint8_t>& buf, const bool modify, parseResult& parsed){
  uint32_t cur = 0;
  uint32_t prev = NOTFOUND;
  uint32_t len = 0;
  bool first = true;
  for (size_t i = 0; i <= buf.size(); ++i){
    if (first ||
        (i != buf.size() && (buf[i] & 0xC0) == 0x80)){
      cur <<= 8;
      cur += buf[i];
      len++;
      first = false;
      continue;
    }

    uint64_t term = (pt != C_TWOGRAM) ? cur : ((uint64_t)prev << 32) + cur;

    if (pt != C_TWOGRAM || prev != NOTFOUND){
      const uint32_t id = getiID(term, modify);
      if (id == NOTFOUND) return -1;
      const uint32_t offset = static_cast<uint32_t>(i - len);
      parsed.push_back(make_pair(id, offset));
    }

    if (C_TWOGRAM){
      prev = cur;
    }

    if (i == buf.size()) break;
    cur = buf[i]; // cur.clear() 
    len = 1;
  }

  if (pt == C_TWOGRAM && 
      parsed.size() == 0 &&
      prev != NOTFOUND){
    // Special-case: Query is One character
    uint32_t id = NOTFOUND;
    parsed.push_back(make_pair(id, 0));
  }
      
  return 0;
}

最初の(buf[i] & 0xC0) == 0x80の付近はUTF-8単位で1文字とか - yasuhisa's blogのところで、UTF-8を一文字区切りにするために必要なところ。あとはところどころ分からないところがあるので、そこを調べる。

    uint64_t term = (pt != C_TWOGRAM) ? cur : ((uint64_t)prev << 32) + cur;

とりあえずBigramかどうかで処理が分かれてて、Bigramじゃない(=Unigram)ときはcurをそのまま採用(uint32_tからuint64_tへはどうやって変換されているのかあとで調べる)。Bigramのときの処理がよく分かってない。prevを32ビット左にシフトしてcurと足し算をしている。何でこんなことをしているのかよく分からないので、コードを書いてみる。

#include <iostream>
#include <bitset>
int main(int argc, char *argv[]) {
  uint32_t prev = 1;
  uint64_t cur = 2;
  uint64_t term = ((uint64_t) prev << 32) + cur;
  std::cout << "prev : " << prev << std::endl;
  std::cout << "cur : " << cur << std::endl;
  std::cout << "term : " << term << std::endl;
  return 0;
}

結果はこんな感じ。

/Users/syou6162/cpp% ./a.out
prev : 1
cur : 2
term : 4294967298

まずprev(=1)をuint64_tに型の変換をして、32ビット左にシフト(つまり2^32を掛ける)する。すると4294967296になる。これにcur(=2)を足したのがterm。ここでようやく分かってきて、32ビット左にシフトする(4294967296をかける)っていうこととuint32_tの上限が4,294,967,295であるということが結びついた。

どうでもいいけど、ビットシフトもろくに分かってない感じだったので、C++実践プログラミングとか見てた。普通にかけ算するよりもビットシフトならずらせばいいだけなので、高速ということだそうだ。