diff options
Diffstat (limited to 'vendor/github.com/ulikunitz/xz/internal/hash')
4 files changed, 290 insertions, 0 deletions
diff --git a/vendor/github.com/ulikunitz/xz/internal/hash/cyclic_poly.go b/vendor/github.com/ulikunitz/xz/internal/hash/cyclic_poly.go new file mode 100644 index 0000000..a328878 --- /dev/null +++ b/vendor/github.com/ulikunitz/xz/internal/hash/cyclic_poly.go | |||
@@ -0,0 +1,181 @@ | |||
1 | // Copyright 2014-2017 Ulrich Kunitz. All rights reserved. | ||
2 | // Use of this source code is governed by a BSD-style | ||
3 | // license that can be found in the LICENSE file. | ||
4 | |||
5 | package hash | ||
6 | |||
7 | // CyclicPoly provides a cyclic polynomial rolling hash. | ||
8 | type CyclicPoly struct { | ||
9 | h uint64 | ||
10 | p []uint64 | ||
11 | i int | ||
12 | } | ||
13 | |||
14 | // ror rotates the unsigned 64-bit integer to right. The argument s must be | ||
15 | // less than 64. | ||
16 | func ror(x uint64, s uint) uint64 { | ||
17 | return (x >> s) | (x << (64 - s)) | ||
18 | } | ||
19 | |||
20 | // NewCyclicPoly creates a new instance of the CyclicPoly structure. The | ||
21 | // argument n gives the number of bytes for which a hash will be executed. | ||
22 | // This number must be positive; the method panics if this isn't the case. | ||
23 | func NewCyclicPoly(n int) *CyclicPoly { | ||
24 | if n < 1 { | ||
25 | panic("argument n must be positive") | ||
26 | } | ||
27 | return &CyclicPoly{p: make([]uint64, 0, n)} | ||
28 | } | ||
29 | |||
30 | // Len returns the length of the byte sequence for which a hash is generated. | ||
31 | func (r *CyclicPoly) Len() int { | ||
32 | return cap(r.p) | ||
33 | } | ||
34 | |||
35 | // RollByte hashes the next byte and returns a hash value. The complete becomes | ||
36 | // available after at least Len() bytes have been hashed. | ||
37 | func (r *CyclicPoly) RollByte(x byte) uint64 { | ||
38 | y := hash[x] | ||
39 | if len(r.p) < cap(r.p) { | ||
40 | r.h = ror(r.h, 1) ^ y | ||
41 | r.p = append(r.p, y) | ||
42 | } else { | ||
43 | r.h ^= ror(r.p[r.i], uint(cap(r.p)-1)) | ||
44 | r.h = ror(r.h, 1) ^ y | ||
45 | r.p[r.i] = y | ||
46 | r.i = (r.i + 1) % cap(r.p) | ||
47 | } | ||
48 | return r.h | ||
49 | } | ||
50 | |||
51 | // Stores the hash for the individual bytes. | ||
52 | var hash = [256]uint64{ | ||
53 | 0x2e4fc3f904065142, 0xc790984cfbc99527, | ||
54 | 0x879f95eb8c62f187, 0x3b61be86b5021ef2, | ||
55 | 0x65a896a04196f0a5, 0xc5b307b80470b59e, | ||
56 | 0xd3bff376a70df14b, 0xc332f04f0b3f1701, | ||
57 | 0x753b5f0e9abf3e0d, 0xb41538fdfe66ef53, | ||
58 | 0x1906a10c2c1c0208, 0xfb0c712a03421c0d, | ||
59 | 0x38be311a65c9552b, 0xfee7ee4ca6445c7e, | ||
60 | 0x71aadeded184f21e, 0xd73426fccda23b2d, | ||
61 | 0x29773fb5fb9600b5, 0xce410261cd32981a, | ||
62 | 0xfe2848b3c62dbc2d, 0x459eaaff6e43e11c, | ||
63 | 0xc13e35fc9c73a887, 0xf30ed5c201e76dbc, | ||
64 | 0xa5f10b3910482cea, 0x2945d59be02dfaad, | ||
65 | 0x06ee334ff70571b5, 0xbabf9d8070f44380, | ||
66 | 0xee3e2e9912ffd27c, 0x2a7118d1ea6b8ea7, | ||
67 | 0x26183cb9f7b1664c, 0xea71dac7da068f21, | ||
68 | 0xea92eca5bd1d0bb7, 0x415595862defcd75, | ||
69 | 0x248a386023c60648, 0x9cf021ab284b3c8a, | ||
70 | 0xfc9372df02870f6c, 0x2b92d693eeb3b3fc, | ||
71 | 0x73e799d139dc6975, 0x7b15ae312486363c, | ||
72 | 0xb70e5454a2239c80, 0x208e3fb31d3b2263, | ||
73 | 0x01f563cabb930f44, 0x2ac4533d2a3240d8, | ||
74 | 0x84231ed1064f6f7c, 0xa9f020977c2a6d19, | ||
75 | 0x213c227271c20122, 0x09fe8a9a0a03d07a, | ||
76 | 0x4236dc75bcaf910c, 0x460a8b2bead8f17e, | ||
77 | 0xd9b27be1aa07055f, 0xd202d5dc4b11c33e, | ||
78 | 0x70adb010543bea12, 0xcdae938f7ea6f579, | ||
79 | 0x3f3d870208672f4d, 0x8e6ccbce9d349536, | ||
80 | 0xe4c0871a389095ae, 0xf5f2a49152bca080, | ||
81 | 0x9a43f9b97269934e, 0xc17b3753cb6f475c, | ||
82 | 0xd56d941e8e206bd4, 0xac0a4f3e525eda00, | ||
83 | 0xa06d5a011912a550, 0x5537ed19537ad1df, | ||
84 | 0xa32fe713d611449d, 0x2a1d05b47c3b579f, | ||
85 | 0x991d02dbd30a2a52, 0x39e91e7e28f93eb0, | ||
86 | 0x40d06adb3e92c9ac, 0x9b9d3afde1c77c97, | ||
87 | 0x9a3f3f41c02c616f, 0x22ecd4ba00f60c44, | ||
88 | 0x0b63d5d801708420, 0x8f227ca8f37ffaec, | ||
89 | 0x0256278670887c24, 0x107e14877dbf540b, | ||
90 | 0x32c19f2786ac1c05, 0x1df5b12bb4bc9c61, | ||
91 | 0xc0cac129d0d4c4e2, 0x9fdb52ee9800b001, | ||
92 | 0x31f601d5d31c48c4, 0x72ff3c0928bcaec7, | ||
93 | 0xd99264421147eb03, 0x535a2d6d38aefcfe, | ||
94 | 0x6ba8b4454a916237, 0xfa39366eaae4719c, | ||
95 | 0x10f00fd7bbb24b6f, 0x5bd23185c76c84d4, | ||
96 | 0xb22c3d7e1b00d33f, 0x3efc20aa6bc830a8, | ||
97 | 0xd61c2503fe639144, 0x30ce625441eb92d3, | ||
98 | 0xe5d34cf359e93100, 0xa8e5aa13f2b9f7a5, | ||
99 | 0x5c2b8d851ca254a6, 0x68fb6c5e8b0d5fdf, | ||
100 | 0xc7ea4872c96b83ae, 0x6dd5d376f4392382, | ||
101 | 0x1be88681aaa9792f, 0xfef465ee1b6c10d9, | ||
102 | 0x1f98b65ed43fcb2e, 0x4d1ca11eb6e9a9c9, | ||
103 | 0x7808e902b3857d0b, 0x171c9c4ea4607972, | ||
104 | 0x58d66274850146df, 0x42b311c10d3981d1, | ||
105 | 0x647fa8c621c41a4c, 0xf472771c66ddfedc, | ||
106 | 0x338d27e3f847b46b, 0x6402ce3da97545ce, | ||
107 | 0x5162db616fc38638, 0x9c83be97bc22a50e, | ||
108 | 0x2d3d7478a78d5e72, 0xe621a9b938fd5397, | ||
109 | 0x9454614eb0f81c45, 0x395fb6e742ed39b6, | ||
110 | 0x77dd9179d06037bf, 0xc478d0fee4d2656d, | ||
111 | 0x35d9d6cb772007af, 0x83a56e92c883f0f6, | ||
112 | 0x27937453250c00a1, 0x27bd6ebc3a46a97d, | ||
113 | 0x9f543bf784342d51, 0xd158f38c48b0ed52, | ||
114 | 0x8dd8537c045f66b4, 0x846a57230226f6d5, | ||
115 | 0x6b13939e0c4e7cdf, 0xfca25425d8176758, | ||
116 | 0x92e5fc6cd52788e6, 0x9992e13d7a739170, | ||
117 | 0x518246f7a199e8ea, 0xf104c2a71b9979c7, | ||
118 | 0x86b3ffaabea4768f, 0x6388061cf3e351ad, | ||
119 | 0x09d9b5295de5bbb5, 0x38bf1638c2599e92, | ||
120 | 0x1d759846499e148d, 0x4c0ff015e5f96ef4, | ||
121 | 0xa41a94cfa270f565, 0x42d76f9cb2326c0b, | ||
122 | 0x0cf385dd3c9c23ba, 0x0508a6c7508d6e7a, | ||
123 | 0x337523aabbe6cf8d, 0x646bb14001d42b12, | ||
124 | 0xc178729d138adc74, 0xf900ef4491f24086, | ||
125 | 0xee1a90d334bb5ac4, 0x9755c92247301a50, | ||
126 | 0xb999bf7c4ff1b610, 0x6aeeb2f3b21e8fc9, | ||
127 | 0x0fa8084cf91ac6ff, 0x10d226cf136e6189, | ||
128 | 0xd302057a07d4fb21, 0x5f03800e20a0fcc3, | ||
129 | 0x80118d4ae46bd210, 0x58ab61a522843733, | ||
130 | 0x51edd575c5432a4b, 0x94ee6ff67f9197f7, | ||
131 | 0x765669e0e5e8157b, 0xa5347830737132f0, | ||
132 | 0x3ba485a69f01510c, 0x0b247d7b957a01c3, | ||
133 | 0x1b3d63449fd807dc, 0x0fdc4721c30ad743, | ||
134 | 0x8b535ed3829b2b14, 0xee41d0cad65d232c, | ||
135 | 0xe6a99ed97a6a982f, 0x65ac6194c202003d, | ||
136 | 0x692accf3a70573eb, 0xcc3c02c3e200d5af, | ||
137 | 0x0d419e8b325914a3, 0x320f160f42c25e40, | ||
138 | 0x00710d647a51fe7a, 0x3c947692330aed60, | ||
139 | 0x9288aa280d355a7a, 0xa1806a9b791d1696, | ||
140 | 0x5d60e38496763da1, 0x6c69e22e613fd0f4, | ||
141 | 0x977fc2a5aadffb17, 0xfb7bd063fc5a94ba, | ||
142 | 0x460c17992cbaece1, 0xf7822c5444d3297f, | ||
143 | 0x344a9790c69b74aa, 0xb80a42e6cae09dce, | ||
144 | 0x1b1361eaf2b1e757, 0xd84c1e758e236f01, | ||
145 | 0x88e0b7be347627cc, 0x45246009b7a99490, | ||
146 | 0x8011c6dd3fe50472, 0xc341d682bffb99d7, | ||
147 | 0x2511be93808e2d15, 0xd5bc13d7fd739840, | ||
148 | 0x2a3cd030679ae1ec, 0x8ad9898a4b9ee157, | ||
149 | 0x3245fef0a8eaf521, 0x3d6d8dbbb427d2b0, | ||
150 | 0x1ed146d8968b3981, 0x0c6a28bf7d45f3fc, | ||
151 | 0x4a1fd3dbcee3c561, 0x4210ff6a476bf67e, | ||
152 | 0xa559cce0d9199aac, 0xde39d47ef3723380, | ||
153 | 0xe5b69d848ce42e35, 0xefa24296f8e79f52, | ||
154 | 0x70190b59db9a5afc, 0x26f166cdb211e7bf, | ||
155 | 0x4deaf2df3c6b8ef5, 0xf171dbdd670f1017, | ||
156 | 0xb9059b05e9420d90, 0x2f0da855c9388754, | ||
157 | 0x611d5e9ab77949cc, 0x2912038ac01163f4, | ||
158 | 0x0231df50402b2fba, 0x45660fc4f3245f58, | ||
159 | 0xb91cc97c7c8dac50, 0xb72d2aafe4953427, | ||
160 | 0xfa6463f87e813d6b, 0x4515f7ee95d5c6a2, | ||
161 | 0x1310e1c1a48d21c3, 0xad48a7810cdd8544, | ||
162 | 0x4d5bdfefd5c9e631, 0xa43ed43f1fdcb7de, | ||
163 | 0xe70cfc8fe1ee9626, 0xef4711b0d8dda442, | ||
164 | 0xb80dd9bd4dab6c93, 0xa23be08d31ba4d93, | ||
165 | 0x9b37db9d0335a39c, 0x494b6f870f5cfebc, | ||
166 | 0x6d1b3c1149dda943, 0x372c943a518c1093, | ||
167 | 0xad27af45e77c09c4, 0x3b6f92b646044604, | ||
168 | 0xac2917909f5fcf4f, 0x2069a60e977e5557, | ||
169 | 0x353a469e71014de5, 0x24be356281f55c15, | ||
170 | 0x2b6d710ba8e9adea, 0x404ad1751c749c29, | ||
171 | 0xed7311bf23d7f185, 0xba4f6976b4acc43e, | ||
172 | 0x32d7198d2bc39000, 0xee667019014d6e01, | ||
173 | 0x494ef3e128d14c83, 0x1f95a152baecd6be, | ||
174 | 0x201648dff1f483a5, 0x68c28550c8384af6, | ||
175 | 0x5fc834a6824a7f48, 0x7cd06cb7365eaf28, | ||
176 | 0xd82bbd95e9b30909, 0x234f0d1694c53f6d, | ||
177 | 0xd2fb7f4a96d83f4a, 0xff0d5da83acac05e, | ||
178 | 0xf8f6b97f5585080a, 0x74236084be57b95b, | ||
179 | 0xa25e40c03bbc36ad, 0x6b6e5c14ce88465b, | ||
180 | 0x4378ffe93e1528c5, 0x94ca92a17118e2d2, | ||
181 | } | ||
diff --git a/vendor/github.com/ulikunitz/xz/internal/hash/doc.go b/vendor/github.com/ulikunitz/xz/internal/hash/doc.go new file mode 100644 index 0000000..f99ec22 --- /dev/null +++ b/vendor/github.com/ulikunitz/xz/internal/hash/doc.go | |||
@@ -0,0 +1,14 @@ | |||
1 | // Copyright 2014-2017 Ulrich Kunitz. All rights reserved. | ||
2 | // Use of this source code is governed by a BSD-style | ||
3 | // license that can be found in the LICENSE file. | ||
4 | |||
5 | /* | ||
6 | Package hash provides rolling hashes. | ||
7 | |||
8 | Rolling hashes have to be used for maintaining the positions of n-byte | ||
9 | sequences in the dictionary buffer. | ||
10 | |||
11 | The package provides currently the Rabin-Karp rolling hash and a Cyclic | ||
12 | Polynomial hash. Both support the Hashes method to be used with an interface. | ||
13 | */ | ||
14 | package hash | ||
diff --git a/vendor/github.com/ulikunitz/xz/internal/hash/rabin_karp.go b/vendor/github.com/ulikunitz/xz/internal/hash/rabin_karp.go new file mode 100644 index 0000000..58635b1 --- /dev/null +++ b/vendor/github.com/ulikunitz/xz/internal/hash/rabin_karp.go | |||
@@ -0,0 +1,66 @@ | |||
1 | // Copyright 2014-2017 Ulrich Kunitz. All rights reserved. | ||
2 | // Use of this source code is governed by a BSD-style | ||
3 | // license that can be found in the LICENSE file. | ||
4 | |||
5 | package hash | ||
6 | |||
7 | // A is the default constant for Robin-Karp rolling hash. This is a random | ||
8 | // prime. | ||
9 | const A = 0x97b548add41d5da1 | ||
10 | |||
11 | // RabinKarp supports the computation of a rolling hash. | ||
12 | type RabinKarp struct { | ||
13 | A uint64 | ||
14 | // a^n | ||
15 | aOldest uint64 | ||
16 | h uint64 | ||
17 | p []byte | ||
18 | i int | ||
19 | } | ||
20 | |||
21 | // NewRabinKarp creates a new RabinKarp value. The argument n defines the | ||
22 | // length of the byte sequence to be hashed. The default constant will will be | ||
23 | // used. | ||
24 | func NewRabinKarp(n int) *RabinKarp { | ||
25 | return NewRabinKarpConst(n, A) | ||
26 | } | ||
27 | |||
28 | // NewRabinKarpConst creates a new RabinKarp value. The argument n defines the | ||
29 | // length of the byte sequence to be hashed. The argument a provides the | ||
30 | // constant used to compute the hash. | ||
31 | func NewRabinKarpConst(n int, a uint64) *RabinKarp { | ||
32 | if n <= 0 { | ||
33 | panic("number of bytes n must be positive") | ||
34 | } | ||
35 | aOldest := uint64(1) | ||
36 | // There are faster methods. For the small n required by the LZMA | ||
37 | // compressor O(n) is sufficient. | ||
38 | for i := 0; i < n; i++ { | ||
39 | aOldest *= a | ||
40 | } | ||
41 | return &RabinKarp{ | ||
42 | A: a, aOldest: aOldest, | ||
43 | p: make([]byte, 0, n), | ||
44 | } | ||
45 | } | ||
46 | |||
47 | // Len returns the length of the byte sequence. | ||
48 | func (r *RabinKarp) Len() int { | ||
49 | return cap(r.p) | ||
50 | } | ||
51 | |||
52 | // RollByte computes the hash after x has been added. | ||
53 | func (r *RabinKarp) RollByte(x byte) uint64 { | ||
54 | if len(r.p) < cap(r.p) { | ||
55 | r.h += uint64(x) | ||
56 | r.h *= r.A | ||
57 | r.p = append(r.p, x) | ||
58 | } else { | ||
59 | r.h -= uint64(r.p[r.i]) * r.aOldest | ||
60 | r.h += uint64(x) | ||
61 | r.h *= r.A | ||
62 | r.p[r.i] = x | ||
63 | r.i = (r.i + 1) % cap(r.p) | ||
64 | } | ||
65 | return r.h | ||
66 | } | ||
diff --git a/vendor/github.com/ulikunitz/xz/internal/hash/roller.go b/vendor/github.com/ulikunitz/xz/internal/hash/roller.go new file mode 100644 index 0000000..ab6a19c --- /dev/null +++ b/vendor/github.com/ulikunitz/xz/internal/hash/roller.go | |||
@@ -0,0 +1,29 @@ | |||
1 | // Copyright 2014-2017 Ulrich Kunitz. All rights reserved. | ||
2 | // Use of this source code is governed by a BSD-style | ||
3 | // license that can be found in the LICENSE file. | ||
4 | |||
5 | package hash | ||
6 | |||
7 | // Roller provides an interface for rolling hashes. The hash value will become | ||
8 | // valid after hash has been called Len times. | ||
9 | type Roller interface { | ||
10 | Len() int | ||
11 | RollByte(x byte) uint64 | ||
12 | } | ||
13 | |||
14 | // Hashes computes all hash values for the array p. Note that the state of the | ||
15 | // roller is changed. | ||
16 | func Hashes(r Roller, p []byte) []uint64 { | ||
17 | n := r.Len() | ||
18 | if len(p) < n { | ||
19 | return nil | ||
20 | } | ||
21 | h := make([]uint64, len(p)-n+1) | ||
22 | for i := 0; i < n-1; i++ { | ||
23 | r.RollByte(p[i]) | ||
24 | } | ||
25 | for i := range h { | ||
26 | h[i] = r.RollByte(p[i+n-1]) | ||
27 | } | ||
28 | return h | ||
29 | } | ||