murmurhash源码分析

  1    /**
  2     * `main.c' - murmurhash
  3     *
  4     * copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
  5     */
  6    
  7    #include <stdio.h>
  8    #include <stdlib.h>
  9    #include <string.h>
 10    #include <unistd.h>
 11    #include <inttypes.h>
 12    #include "murmurhash.h"
 13    
 14    static void
 15    usage () {
 16      fprintf(stderr, "usage: murmur [-hV] [options]\n");
 17    }
 18    
 19    static void   //函数类型和函数名不一行写是什么风格orz...
 20    help () {
 21      fprintf(stderr, "\noptions:\n");
 22      fprintf(stderr, "\n  --seed=[seed]  hash seed (optional)");
 23      fprintf(stderr, "\n");
 24    }
 25    
 26    static char *
 27    read_stdin () {
 28      size_t bsize = 1024;
 29      size_t size = 1;
 30      char buf[bsize];
 31      char *res = (char *) malloc(sizeof(char) * bsize);
 32      char *tmp = NULL;
 33    
 34      // memory issue
 35      if (NULL == res) { return NULL; } //申请内存失败了...
 36    
 37      // cap
 38      res[0] = '\0';
 39    
 40      // read
 41      if (NULL != fgets(buf, bsize, stdin)) {
 42        // store
 43        tmp = res; //异常安全？ 
 44        // resize
 45        size += (size_t) strlen(buf);
 46        // realloc
 47        res = (char *) realloc(res, size);
 48    
 49        // memory issues
 50        if (NULL == res) {
 51          free(tmp);
 52          return NULL;
 53        }
 54    
 55        // yield
 56        strcat(res, buf); //将buf连接到res后面...
 57      //  printf("buf:%s res:%s\n",buf,res);
 58        return res;
 59      }
 60    
 61      free(res);
 62    
 63    
 64      return NULL;
 65    }
 66    
 67    #define isopt(opt, str) (0 == strncmp(opt, str, strlen(str))) 
 68    //比较opt和str前strlen(str)个字符。
 69    
 70    #define setopt(opt, key, var) {                       \
 71        char tmp = 0;                                     \
 72        size_t len = strlen(key) + 1;                     \
 73        for (int i = 0; i < len; ++i) { tmp = *opt++; }   \
 74        var = opt;                                        \
 75    }
 76    // key是"seed",让len = strlen(key)+1，是为了把seed和‘=’跳过去。。。
 77    // 因此seed，‘=’，后面的数字之间不支持有空格。
 78    // 得到的var是*char型的seed.
 79    
 80    
 81    int
 82    main (int argc, char **argv) { //argc是命令行的参数个数，**argv是字符串数组
 83      char *buf = NULL;
 84      char *key = NULL;
 85      char *seed = NULL;
 86      uint32_t h = 0;
 87    
 88      // parse opts
 89      {
 90        char *opt = NULL;
 91        char tmp = 0;
 92    
 93     //   for ( int i = 0 ;  i < argc ; i++)  printf("Argument %d is %s.\n", i, argv[i]);
 94        opt = *argv++; // unused，因为第0个参数就是“murmur”，跳过。
 95        
 96    
 97        while ((opt = *argv++)) { //argv参数最后会变成null,退出循环...
 98    //	printf("opt: %s argv:%s\n",opt,*argv);
 99    
100          // flags
101          if ('-' == *opt++) {
102            switch (*opt++) {
103              case 'h':
104                return usage(), help(), 0; //直接用了return和逗号表达式...避免了break，代码简洁了（？
105    
106              case 'V':
107                fprintf(stderr, "%s\n", MURMURHASH_VERSION);
108                return 0;
109    
110              case '-': //参数不要带空格。。。
111                if (isopt(opt, "seed")) {
112                  setopt(opt, "seed", seed);
113                }
114                break; //是break而不是return，说明在--seed参数后面还可以跟其他参数。。
115    		    //如果跟了多了--seed参数，前面的参数会被最有一个覆盖掉，hash结果与最后一个seed对应。
116              default:
117                tmp = *opt--;//这个tmp好像没什么用啊？
118                // error
119                fprintf(stderr, "unknown option: `%s'\n", opt);
120                usage();
121                return 1;
122            }
123          }
124        }
125      }
126    
127      if (NULL == seed) { //赞！ 避免了手残把等号写成赋值号的可能，下面也都用了这种写法。
128        seed = "0";
129      }
130    
131    #define hash(key) murmurhash(key, (uint32_t) strlen(key), (uint32_t) atoi(seed));
132    						//atoi，把字符串转成了int型，然后被强转了。。。
133      if (1 == isatty(0)) { return 1; } //isatty 判断文件描述词是否位终端机（？，是为1，不是为0
134      else if (ferror(stdin)) { return 1; }
135      else {
136        buf = read_stdin();
137        if (NULL == buf) { return 1; }
138        else if (0 == strlen(buf)) { buf = ""; }
139        h = hash(buf);
140        printf("%" PRIu32 "\n", h);
141        //PRIu32是头文件inttypes.h包含的宏，用于平台独立的printf编码。。
142        //会自动根据平台去对应相应的类型说明符。。。
143        do {
144          key = read_stdin();
145          if (NULL == key) { break; }
146          else if (0 == strlen(buf)) { buf = ""; }
147          h = hash(buf);
148          printf("%d" PRIu32 "\n", h);
149        } while (NULL != key);
150      }
151    
152    #undef hash
153    
154      return 0;
155    }
156
157
158
159    
160    /**
161     * `murmurhash.h' - murmurhash
162     *
163     * copyright (c) 2014 joseph werle <joseph.werle@gmail.com>
164     */
165    
166    #include <stdlib.h>
167    #include <stdio.h>
168    #include <stdint.h>
169    #include "murmurhash.h"
170    
171    uint32_t
172    murmurhash (const char *key, uint32_t len, uint32_t seed) {
173      uint32_t c1 = 0xcc9e2d51;
174      uint32_t c2 = 0x1b873593;
175      uint32_t r1 = 15;
176      uint32_t r2 = 13;
177      uint32_t m = 5;
178      uint32_t n = 0xe6546b64;
179      uint32_t h = 0;
180      uint32_t k = 0;
181      uint8_t *d = (uint8_t *) key; // 32 bit extract from `key'
182      const uint32_t *chunks = NULL;
183      const uint8_t *tail = NULL; // tail - last 8 bytes
184      int i = 0;
185      int l = len / 4; // chunk length
186    
187      h = seed;
188    
189      chunks = (const uint32_t *) (d + l * 4); // body
190      tail = (const uint8_t *) (d + l * 4); // last 8 byte chunk of `key'
191    
192      // for each 4 byte chunk of `key'
193      for (i = -l; i != 0; ++i) {
194        // next 4 byte chunk of `key'
195        k = chunks[i];
196    
197        // encode next 4 byte chunk of `key'
198        k *= c1;
199        k = (k << r1) | (k >> (32 - r1));
200        k *= c2;
201    
202        // append to hash
203        h ^= k;
204        h = (h << r2) | (h >> (32 - r2));
205        h = h * m + n;
206      }
207    
208      k = 0;
209    
210      // remainder
211      switch (len & 3) { // `len % 4'
212        case 3: k ^= (tail[2] << 16);
213        case 2: k ^= (tail[1] << 8);
214    
215        case 1:
216          k ^= tail[0];
217          k *= c1;
218          k = (k << r1) | (k >> (32 - r1));
219          k *= c2;
220          h ^= k;
221      }
222    
223      h ^= len;
224    
225      h ^= (h >> 16);
226      h *= 0x85ebca6b;
227      h ^= (h >> 13);
228      h *= 0xc2b2ae35;
229      h ^= (h >> 16);
230    
231      return h;
232    }
233
234