LCOV - code coverage report
Current view: top level - libavutil - murmur3.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 74 82 90.2 %
Date: 2017-12-15 02:19:58 Functions: 10 10 100.0 %

          Line data    Source code
       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           2 : AVMurMur3 *av_murmur3_alloc(void)
      33             : {
      34           2 :     return av_mallocz(sizeof(AVMurMur3));
      35             : }
      36             : 
      37         260 : void av_murmur3_init_seeded(AVMurMur3 *c, uint64_t seed)
      38             : {
      39         260 :     memset(c, 0, sizeof(*c));
      40         260 :     c->h1 = c->h2 = seed;
      41         260 : }
      42             : 
      43           3 : void av_murmur3_init(AVMurMur3 *c)
      44             : {
      45             :     // arbitrary random number as seed
      46           3 :     av_murmur3_init_seeded(c, 0x725acc55daddca55);
      47           3 : }
      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        2448 : static uint64_t inline get_k1(const uint8_t *src)
      55             : {
      56        2448 :     uint64_t k = AV_RL64(src);
      57        2448 :     k *= c1;
      58        2448 :     k = ROT(k, 31);
      59        2448 :     k *= c2;
      60        2448 :     return k;
      61             : }
      62             : 
      63        2448 : static inline uint64_t get_k2(const uint8_t *src)
      64             : {
      65        2448 :     uint64_t k = AV_RL64(src + 8);
      66        2448 :     k *= c2;
      67        2448 :     k = ROT(k, 33);
      68        2448 :     k *= c1;
      69        2448 :     return k;
      70             : }
      71             : 
      72        2188 : static inline uint64_t update_h1(uint64_t k, uint64_t h1, uint64_t h2)
      73             : {
      74        2188 :     k ^= h1;
      75        2188 :     k = ROT(k, 27);
      76        2188 :     k += h2;
      77        2188 :     k *= 5;
      78        2188 :     k += 0x52dce729;
      79        2188 :     return k;
      80             : }
      81             : 
      82        2188 : static inline uint64_t update_h2(uint64_t k, uint64_t h1, uint64_t h2)
      83             : {
      84        2188 :     k ^= h2;
      85        2188 :     k = ROT(k, 31);
      86        2188 :     k += h1;
      87        2188 :     k *= 5;
      88        2188 :     k += 0x38495ab5;
      89        2188 :     return k;
      90             : }
      91             : 
      92         260 : void av_murmur3_update(AVMurMur3 *c, const uint8_t *src, int len)
      93             : {
      94             :     const uint8_t *end;
      95         260 :     uint64_t h1 = c->h1, h2 = c->h2;
      96             :     uint64_t k1, k2;
      97         260 :     if (len <= 0) return;
      98         259 :     c->len += len;
      99         259 :     if (c->state_pos > 0) {
     100           0 :         while (c->state_pos < 16) {
     101           0 :             c->state[c->state_pos++] = *src++;
     102           0 :             if (--len <= 0) return;
     103             :         }
     104           0 :         c->state_pos = 0;
     105           0 :         k1 = get_k1(c->state);
     106           0 :         k2 = get_k2(c->state);
     107           0 :         h1 = update_h1(k1, h1, h2);
     108           0 :         h2 = update_h2(k2, h1, h2);
     109             :     }
     110             : 
     111         259 :     end = src + (len & ~15);
     112        2706 :     while (src < end) {
     113             :         // These could be done sequentially instead
     114             :         // of interleaved, but like this is over 10% faster
     115        2188 :         k1 = get_k1(src);
     116        2188 :         k2 = get_k2(src);
     117        2188 :         h1 = update_h1(k1, h1, h2);
     118        2188 :         h2 = update_h2(k2, h1, h2);
     119        2188 :         src += 16;
     120             :     }
     121         259 :     c->h1 = h1;
     122         259 :     c->h2 = h2;
     123             : 
     124         259 :     len &= 15;
     125         259 :     if (len > 0) {
     126         240 :         memcpy(c->state, src, len);
     127         240 :         c->state_pos = len;
     128             :     }
     129             : }
     130             : 
     131         520 : static inline uint64_t fmix(uint64_t k)
     132             : {
     133         520 :     k ^= k >> 33;
     134         520 :     k *= UINT64_C(0xff51afd7ed558ccd);
     135         520 :     k ^= k >> 33;
     136         520 :     k *= UINT64_C(0xc4ceb9fe1a85ec53);
     137         520 :     k ^= k >> 33;
     138         520 :     return k;
     139             : }
     140             : 
     141         260 : void av_murmur3_final(AVMurMur3 *c, uint8_t dst[16])
     142             : {
     143         260 :     uint64_t h1 = c->h1, h2 = c->h2;
     144         260 :     memset(c->state + c->state_pos, 0, sizeof(c->state) - c->state_pos);
     145         260 :     h1 ^= get_k1(c->state) ^ c->len;
     146         260 :     h2 ^= get_k2(c->state) ^ c->len;
     147         260 :     h1 += h2;
     148         260 :     h2 += h1;
     149         260 :     h1 = fmix(h1);
     150         260 :     h2 = fmix(h2);
     151         260 :     h1 += h2;
     152         260 :     h2 += h1;
     153         260 :     AV_WL64(dst, h1);
     154         260 :     AV_WL64(dst + 8, h2);
     155         260 : }

Generated by: LCOV version 1.13