Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. /*
  2.  * Copyright (C) 2013 Reimar Döffinger <Reimar.Doeffinger@gmx.de>
  3.  *
  4.  * This file is part of FFmpeg.
  5.  *
  6.  * FFmpeg is free software; you can redistribute it and/or
  7.  * modify it under the terms of the GNU Lesser General Public
  8.  * License as published by the Free Software Foundation; either
  9.  * version 2.1 of the License, or (at your option) any later version.
  10.  *
  11.  * FFmpeg is distributed in the hope that it will be useful,
  12.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14.  * Lesser General Public License for more details.
  15.  *
  16.  * You should have received a copy of the GNU Lesser General Public
  17.  * License along with FFmpeg; if not, write to the Free Software
  18.  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  19.  */
  20. #include <stdint.h>
  21. #include "mem.h"
  22. #include "intreadwrite.h"
  23. #include "murmur3.h"
  24.  
  25. typedef struct AVMurMur3 {
  26.     uint64_t h1, h2;
  27.     uint8_t state[16];
  28.     int state_pos;
  29.     uint64_t len;
  30. } AVMurMur3;
  31.  
  32. AVMurMur3 *av_murmur3_alloc(void)
  33. {
  34.     return av_mallocz(sizeof(AVMurMur3));
  35. }
  36.  
  37. void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
  38. {
  39.     memset(c, 0, sizeof(*c));
  40.     c->h1 = c->h2 = seed;
  41. }
  42.  
  43. void av_murmur3_init(AVMurMur3 *c)
  44. {
  45.     // arbitrary random number as seed
  46.     av_murmur3_init_seeded(c, 0x725acc55daddca55);
  47. }
  48.  
  49. static const uint64_t c1 = UINT64_C(0x87c37b91114253d5);
  50. static const uint64_t c2 = UINT64_C(0x4cf5ad432745937f);
  51.  
  52. #define ROT(a, b) ((a << b) | (a >> (64 - b)))
  53.  
  54. static uint64_t inline get_k1(const uint8_t *src)
  55. {
  56.     uint64_t k = AV_RL64(src);
  57.     k *= c1;
  58.     k = ROT(k, 31);
  59.     k *= c2;
  60.     return k;
  61. }
  62.  
  63. static uint64_t inline get_k2(const uint8_t *src)
  64. {
  65.     uint64_t k = AV_RL64(src + 8);
  66.     k *= c2;
  67.     k = ROT(k, 33);
  68.     k *= c1;
  69.     return k;
  70. }
  71.  
  72. static uint64_t inline update_h1(uint64_t k, uint64_t h1, uint64_t h2)
  73. {
  74.     k ^= h1;
  75.     k = ROT(k, 27);
  76.     k += h2;
  77.     k *= 5;
  78.     k += 0x52dce729;
  79.     return k;
  80. }
  81.  
  82. static uint64_t inline update_h2(uint64_t k, uint64_t h1, uint64_t h2)
  83. {
  84.     k ^= h2;
  85.     k = ROT(k, 31);
  86.     k += h1;
  87.     k *= 5;
  88.     k += 0x38495ab5;
  89.     return k;
  90. }
  91.  
  92. void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
  93. {
  94.     const uint8_t *end;
  95.     uint64_t h1 = c->h1, h2 = c->h2;
  96.     uint64_t k1, k2;
  97.     if (len <= 0) return;
  98.     c->len += len;
  99.     if (c->state_pos > 0) {
  100.         while (c->state_pos < 16) {
  101.             c->state[c->state_pos++] = *src++;
  102.             if (--len <= 0) return;
  103.         }
  104.         c->state_pos = 0;
  105.         k1 = get_k1(c->state);
  106.         k2 = get_k2(c->state);
  107.         h1 = update_h1(k1, h1, h2);
  108.         h2 = update_h2(k2, h1, h2);
  109.     }
  110.  
  111.     end = src + (len & ~15);
  112.     while (src < end) {
  113.         // These could be done sequentially instead
  114.         // of interleaved, but like this is over 10% faster
  115.         k1 = get_k1(src);
  116.         k2 = get_k2(src);
  117.         h1 = update_h1(k1, h1, h2);
  118.         h2 = update_h2(k2, h1, h2);
  119.         src += 16;
  120.     }
  121.     c->h1 = h1;
  122.     c->h2 = h2;
  123.  
  124.     len &= 15;
  125.     if (len > 0) {
  126.         memcpy(c->state, src, len);
  127.         c->state_pos = len;
  128.     }
  129. }
  130.  
  131. static inline uint64_t fmix(uint64_t k)
  132. {
  133.     k ^= k >> 33;
  134.     k *= UINT64_C(0xff51afd7ed558ccd);
  135.     k ^= k >> 33;
  136.     k *= UINT64_C(0xc4ceb9fe1a85ec53);
  137.     k ^= k >> 33;
  138.     return k;
  139. }
  140.  
  141. void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
  142. {
  143.     uint64_t h1 = c->h1, h2 = c->h2;
  144.     memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
  145.     h1 ^= get_k1(c->state) ^ c->len;
  146.     h2 ^= get_k2(c->state) ^ c->len;
  147.     h1 += h2;
  148.     h2 += h1;
  149.     h1 = fmix(h1);
  150.     h2 = fmix(h2);
  151.     h1 += h2;
  152.     h2 += h1;
  153.     AV_WL64(dst, h1);
  154.     AV_WL64(dst + 8, h2);
  155. }
  156.  
  157. #ifdef TEST
  158. int main(void)
  159. {
  160.     int i;
  161.     uint8_t hash_result[16] = {0};
  162.     AVMurMur3 *ctx = av_murmur3_alloc();
  163. #if 1
  164.     uint8_t in[256] = {0};
  165.     uint8_t *hashes = av_mallocz(256 * 16);
  166.     for (i = 0; i < 256; i++)
  167.     {
  168.         in[i] = i;
  169.         av_murmur3_init_seeded(ctx, 256 - i);
  170.         // Note: this actually tests hashing 0 bytes
  171.         av_murmur3_update(ctx, in, i);
  172.         av_murmur3_final(ctx, hashes + 16 * i);
  173.     }
  174.     av_murmur3_init_seeded(ctx, 0);
  175.     av_murmur3_update(ctx, hashes, 256 * 16);
  176.     av_murmur3_final(ctx, hash_result);
  177.     av_free(hashes);
  178.     av_freep(&ctx);
  179.     printf("result: 0x%"PRIx64" 0x%"PRIx64"\n", AV_RL64(hash_result), AV_RL64(hash_result + 8));
  180.     // official reference value is 32 bit
  181.     return AV_RL32(hash_result) != 0x6384ba69;
  182. #else
  183.     uint8_t *in = av_mallocz(512*1024);
  184.     av_murmur3_init(ctx);
  185.     for (i = 0; i < 40*1024; i++)
  186.         av_murmur3_update(ctx, in, 512*1024);
  187.     av_murmur3_final(ctx, hash_result);
  188.     av_free(in);
  189.     return hash_result[0];
  190. #endif
  191. }
  192. #endif
  193.