← Back to branch summary

~ppsspp/ppsspp/ppsspp_1.3.0

« back to all changes in this revision

Viewing changes to ext/native/util/hash/hash.cpp

  • Committer: Sérgio Benjamim
  • Date: 2017-01-02 00:12:05 UTC
  • Revision ID: sergio_br2@yahoo.com.br-20170102001205-cxbta9za203nmjwm
1.3.0 source (from ppsspp_1.3.0-r160.p5.l1762.a165.t83~56~ubuntu16.04.1.tar.xz).

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/native/util/hash/hash.cpp
 
1
#include "base/basictypes.h"
 
2
#include "util/hash/hash.h"
 
3
 
 
4
namespace hash {
 
5
 
 
6
// uint32_t
 
7
// WARNING - may read one more byte! Fine if the input is a null-terminated string.
 
8
// Implementation from Wikipedia.
 
9
uint32_t Fletcher(const uint8_t *data_uint8, size_t length) {
 
10
  const uint16_t *data = (const uint16_t *)data_uint8;
 
11
  size_t len = (length + 1) / 2;
 
12
  uint32_t sum1 = 0xffff, sum2 = 0xffff;
 
13
 
 
14
  while (len) {
 
15
    size_t tlen = len > 360 ? 360 : len;
 
16
    len -= tlen;
 
17
 
 
18
    do {
 
19
      sum1 += *data++;
 
20
      sum2 += sum1;
 
21
    } while (--tlen);
 
22
 
 
23
    sum1 = (sum1 & 0xffff) + (sum1 >> 16);
 
24
    sum2 = (sum2 & 0xffff) + (sum2 >> 16);
 
25
  }
 
26
 
 
27
  /* Second reduction step to reduce sums to 16 bits */
 
28
  sum1 = (sum1 & 0xffff) + (sum1 >> 16);
 
29
  sum2 = (sum2 & 0xffff) + (sum2 >> 16);
 
30
  return sum2 << 16 | sum1;
 
31
}
 
32
 
 
33
// Implementation from Wikipedia
 
34
// Slightly slower than Fletcher above, but slighly more reliable.
 
35
#define MOD_ADLER 65521
 
36
// data: Pointer to the data to be summed; len is in bytes
 
37
uint32_t Adler32(const uint8_t *data, size_t len) {
 
38
  uint32_t a = 1, b = 0;
 
39
  while (len) {
 
40
    size_t tlen = len > 5550 ? 5550 : len;
 
41
    len -= tlen;
 
42
    do {
 
43
      a += *data++;
 
44
      b += a;
 
45
    } while (--tlen);
 
46
 
 
47
    a = (a & 0xffff) + (a >> 16) * (65536 - MOD_ADLER);
 
48
    b = (b & 0xffff) + (b >> 16) * (65536 - MOD_ADLER);
 
49
  }
 
50
 
 
51
  // It can be shown that a <= 0x1013a here, so a single subtract will do.
 
52
  if (a >= MOD_ADLER) {
 
53
    a -= MOD_ADLER;
 
54
  }
 
55
 
 
56
  // It can be shown that b can reach 0xfff87 here.
 
57
  b = (b & 0xffff) + (b >> 16) * (65536 - MOD_ADLER);
 
58
 
 
59
  if (b >= MOD_ADLER) {
 
60
    b -= MOD_ADLER;
 
61
  }
 
62
  return (b << 16) | a;
 
63
}
 
64
 
 
65
}  // namespace hash