Digest-FP56x1xor.xs

filter: Statementstmt 43.5% 47 / 108 Branchbran 12.7% 11 / 86 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 29.9% 58 / 194 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Digest/mkrandomtable.pl ↑ Summary blib/lib/Digest/FP56x1xor.pm »
1 /*
2 * Digest::FP56x1xor.xs - C implementation of a 56bit pseudo additive fingerprint hash.
3 *
4 * (C) 2007-2008 jw@suse.de, Novell Inc.
5 * This module is free software. IT may be used
6 * and/or modified under the same terms as perl itself.
7 *
8 * See also
9 * perldoc perlxs
10 * perldoc perlguts
11 * perldoc perlxstut
12 * perldoc perlapi
13 *
14 * Currently gen_l() croaks, if no 64bit integers are available
15 * and gen() is suggested, which returns a hex string.
16 * If the compiler does not respond to 'long long' with 64bit,
17 * we die().
18 *
19 */
20 #include "EXTERN.h"
21 #include "perl.h"
22 #include "XSUB.h"
23  
24 #include "ppport.h"
25  
26 #define VERSION "0.15" // keep in sync with Changes, lib/Digest/FP56x1xor.pm
27  
28 #if !defined(_STDINT_H) && !defined(__WORDSIZE)
29 // stdint.h and bits/types.h also have these:
30 typedef unsigned long long uint64_t;
31 typedef unsigned int uint32_t;
32 #endif
33  
34 static uint64_t rand56[256] = {
35 #include "random56x256.h"
36 };
37  
38 // rotate56 rotates the lower 56 bits in h by m bits.
39 // The high 8 bit of h are cleared and remain zero.
40 5 static uint64_t rotate56(uint64_t h, int m)
41 {
42 5 uint64_t x = (h << m) & 0x00ffffffffffffffLL;
43 5 h &= 0x00ffffffffffffffLL;
44 5 x |= (h >> (56-m));
45 5 return x;
46 }
47  
48 #if 0
49 // hmm, is this useful? how ould perl work with that
50 // string? I need to push it into
51 // postgresql and sqlite databases and have it compared there.
52 // the sql statements for this are always 7bit ascii, right?
53 //
54 static unsigned char *uint64tostr8(uint64_t h, unsigned char *buf)
55 {
56 unsigned char buf8[9];
57 int i;
58 if (!buf) buf = buf8;
59 for (i = 0; i < 8; i++)
60 {
61 buf[i] = (unsigned char)((h>>(8*(7-i))) & 0xff);
62 }
63 return buf;
64 }
65 #endif
66  
67 // fp is a 64bit integer.
68 // highest 2 bit are always zero, next 6 bit are the modulo count.
69 // remaining lower 56 bit are fingerprint hash value.
70 3 static uint64_t gen_fp(const char *text, unsigned int len)
71 {
72 3 uint64_t h = 0;
73 3 unsigned int m = 0; // byte counter modulo 56
74 unsigned int c;
75  
76 if (sizeof(uint64_t) != 8)
77 croak("sizeof(uint64_t) is %d, need 8\n", (int)sizeof(uint64_t));
78  
79 7 ▶ while (len-- > 0)
Branch: 1 branch
BranchTrueFalseTotal
while (len-- > 0) 4 3 7
80 {
81 4 c = (unsigned char)*text++;
82 4 uint64_t x = rotate56(rand56[c], m);
83 4 h ^= x;
84 4 ▶ if (++m >= 56) m = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (++m >= 56) m = 0; 0 4 4
85 }
86 3 h |= ((uint64_t)m) << 56;
87 3 return h;
88 }
89  
90 1 static uint64_t cat_fp(uint64_t h1, uint64_t h2)
91 {
92 1 unsigned int m1 = (h1 >> 56);
93 1 unsigned int m2 = (h2 >> 56);
94 1 uint64_t r = rotate56(h2, m1) ^ (h1 & 0x00ffffffffffffffLL);
95 1 m2 += m1;
96 1 ▶ if (m2 >= 56) m2 -= 56;
Branch: 1 branch
BranchTrueFalseTotal
if (m2 >= 56) m2 -= 56; 0 1 1
97 1 r |= ((uint64_t)m2)<<56;
98 1 return r;
99 }
100  
101 32 static int xc2i(unsigned char c)
102 {
103 // ascii has numbers before upper before lower case.
104 32 ▶ if (c <= '9') return c - '0';
Branch: 1 branch
BranchTrueFalseTotal
if (c <= '9') return c - '0'; 24 8 32
105 8 ▶ if (c <= 'F') return c - 'A' + 10;
Branch: 1 branch
BranchTrueFalseTotal
if (c <= 'F') return c - 'A' + 10; 0 8 8
106 8 return c - 'a' + 10;
107 }
108  
109 2 static uint64_t x2i64(unsigned char *t, int n)
110 {
111 2 uint64_t h = 0;
112 34 ▶ while (n-- > 0)
Branch: 1 branch
BranchTrueFalseTotal
while (n-- > 0) 32 2 34
113 32 h = (h<<4) + xc2i(*t++);
114 2 return h;
115 }
116  
117 4 static char *ll2x16(uint64_t fp)
118 {
119 static char buf[18];
120 4 sprintf(buf, "%08x%08x", (unsigned int)(fp>>32), (unsigned int)(fp & 0xffffffff));
121 4 return buf;
122 }
123  
124 #if 0
125 // same as ll2x16, but with 0x prefix
126 // may be used for human consumption. Databases don't like that.
127 static char *ll2x18(uint64_t fp)
128 {
129 static char buf[20];
130 sprintf(buf, "0x%08x%08x", (unsigned int)(fp>>32), (unsigned int)(fp & 0xffffffff));
131 return buf;
132 }
133 #endif
134  
135 1 static uint64_t cat_fp_x(const char *x1, const char *x2)
136 {
137 1 uint64_t h1 = x2i64((unsigned char *)x1, strlen(x1));
138 1 uint64_t h2 = x2i64((unsigned char *)x2, strlen(x2));
139 1 return cat_fp(h1, h2);
140 }
141  
142 // private version of \w, just like perl in ascii C locale.
143 // but also with quote chars, so that <div id="foo" name=bar>
144 // is preserverd during cooked()
145  
146 0 static int is_word_ch_q(int c)
147 {
148 0 ▶ if ((c <= 'z' && c >= 'a') ||
Branch: 3 branches
BranchTrueFalseTotal
if ((c <= 'z' && c >= 'a') || 0 0 0
if ((c <= 'z' && c >= 'a') || 0 0 0
if ((c <= 'z' && c >= 'a') || 0 0 0
149 0 ▶ (c <= 'Z' && c >= 'A') ||
Branch: 2 branches
BranchTrueFalseTotal
(c <= 'Z' && c >= 'A') || 0 0 0
(c <= 'Z' && c >= 'A') || 0 0 0
150 0 ▶ (c <= '9' && c >= '0') ||
Branch: 2 branches
BranchTrueFalseTotal
(c <= '9' && c >= '0') || 0 0 0
(c <= '9' && c >= '0') || 0 0 0
151 0 ▶ c == '_' || c == '"' || c == '\'')
Branch: 2 branches
BranchTrueFalseTotal
c == '_' || c == '"' || c == '\'') 0 0 0
c == '_' || c == '"' || c == '\'') 0 0 0
152 0 return 1;
153 0 return 0;
154 }
155  
156 // called with len including the trailing \n or \f.
157 // returns the number of char written to outp
158 // it never writes more than len chars to out.
159 0 static int cook_text(char *outp, const char *text, int len)
160 {
161 0 char *p = outp;
162 0 char *s = p;
163 0 unsigned char lc = ' '; // last char we sent to output
164 0 int line_start = 1; // we are at start of a line.
165 0 int whitespace = 0; // we saw whitespace chars since lc.
166  
167 0 ▶ while (len-- > 0)
Branch: 1 branch
BranchTrueFalseTotal
while (len-- > 0) 0 0 0
168 {
169 0 unsigned char c = *text++;
170 0 ▶ if (!c) continue; // completly ignore \0 chars
Branch: 1 branch
BranchTrueFalseTotal
if (!c) continue; // completly ignore \0 chars 0 0 0
171  
172 0 ▶ if (line_start && (c == '+' || c == '-' || c == '<' || c == '>'))
Branch: 5 branches
BranchTrueFalseTotal
if (line_start && (c == '+' || c == '-' || c == '<' || c == '>')) 0 0 0
if (line_start && (c == '+' || c == '-' || c == '<' || c == '>')) 0 0 0
if (line_start && (c == '+' || c == '-' || c == '<' || c == '>')) 0 0 0
if (line_start && (c == '+' || c == '-' || c == '<' || c == '>')) 0 0 0
if (line_start && (c == '+' || c == '-' || c == '<' || c == '>')) 0 0 0
173 {
174 0 line_start = 0;
175 0 continue; // ignore typ. diff chars at line start.
176 }
177 0 line_start = 0;
178  
179 0 ▶ if (c <= ' ') // (Whitespace: all character codes <= 32)
Branch: 1 branch
BranchTrueFalseTotal
if (c <= ' ') // (Whitespace: all character codes <= 32) 0 0 0
180 {
181 0 ▶ if (c == '\n' || c == '\r' || c == '\f' || c == '\v')
Branch: 4 branches
BranchTrueFalseTotal
if (c == '\n' || c == '\r' || c == '\f' || c == '\v') 0 0 0
if (c == '\n' || c == '\r' || c == '\f' || c == '\v') 0 0 0
if (c == '\n' || c == '\r' || c == '\f' || c == '\v') 0 0 0
if (c == '\n' || c == '\r' || c == '\f' || c == '\v') 0 0 0
182 0 line_start = 1;
183 0 whitespace = 1;
184 0 continue;
185 }
186  
187 // output a space *only* to prevent run together words.
188 0 ▶ if (whitespace && is_word_ch_q(lc) && is_word_ch_q(c)) *p++ = ' ';
Branch: 3 branches
BranchTrueFalseTotal
if (whitespace && is_word_ch_q(lc) && is_word_ch_q(c)) *p++ = ' '; 0 0 0
if (whitespace && is_word_ch_q(lc) && is_word_ch_q(c)) *p++ = ' '; 0 0 0
if (whitespace && is_word_ch_q(lc) && is_word_ch_q(c)) *p++ = ' '; 0 0 0
189 0 whitespace = 0;
190  
191 // this ~-magic does not really fold utf8 to latin1.
192 // maybe it helps to map other encodings.
193 0 ▶ if (c >= 128)
Branch: 1 branch
BranchTrueFalseTotal
if (c >= 128) 0 0 0
194 {
195 0 ▶ if (lc < 128) *p++ = '~';
Branch: 1 branch
BranchTrueFalseTotal
if (lc < 128) *p++ = '~'; 0 0 0
196 0 lc = c;
197 }
198 else
199 {
200 0 *p++ = lc = c;
201 }
202 }
203  
204 0 return p - s;
205 }
206  
207  
208 MODULE = Digest::FP56x1xor PACKAGE = Digest::FP56x1xor
209 PROTOTYPES: ENABLE
210  
211 long gen_l(text)
212 const char *text
213 CODE:
214 if (sizeof(uint64_t) != 8)
215 croak("sizeof(uint64_t) is %d, need 8. Please try the gen() method\n", (int)sizeof(uint64_t));
216 0 ▶ RETVAL = gen_fp(text, strlen(text));
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = gen_fp(text, strlen(text)); 0 0 0
217 OUTPUT:
218 RETVAL
219  
220 long cat_l(h1, h2)
221 long h1
222 long h2
223 CODE:
224 0 ▶ RETVAL = cat_fp((uint64_t)h1, (uint64_t)h2);
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = cat_fp((uint64_t)h1, (uint64_t)h2); 0 0 0
225 OUTPUT:
226 RETVAL
227  
228 SV *gen(sv_text, ...)
229 SV *sv_text
230 INIT:
231 STRLEN text_len;
232 IV start_off;
233 IV len;
234 const char *text;
235  
236 3 text = (const char *)SvPV(sv_text, text_len);
237 3 ▶ if ( items > 1)
Branch: 1 branch
BranchTrueFalseTotal
if ( items > 1) 0 3 3
238 {
239 0 start_off = SvIV(ST(1));
240 0 ▶ if (start_off > text_len)
Branch: 1 branch
BranchTrueFalseTotal
if (start_off > text_len) 0 0 0
241 0 croak("specified offset=%d is beyond text_len=%d",
242 (int)start_off, (int)text_len);
243 0 text_len -= start_off;
244 }
245 else
246 3 start_off = 0;
247  
248 3 ▶ if ( items > 2)
Branch: 1 branch
BranchTrueFalseTotal
if ( items > 2) 0 3 3
249 {
250 0 len = SvIV(ST(2));
251 0 ▶ if (len > text_len)
Branch: 1 branch
BranchTrueFalseTotal
if (len > text_len) 0 0 0
252 0 croak("specified length=%d exceeds text_len=%d", (int)len, (int)text_len);
253 0 text_len = len;
254 }
255  
256 CODE:
257 3 uint64_t fp = gen_fp(text+start_off, text_len);
258 3 RETVAL = newSVpvn(ll2x16(fp), 16);
259 OUTPUT:
260 RETVAL
261  
262 SV *cat(x1, x2)
263 const char *x1
264 const char *x2
265 CODE:
266 1 uint64_t fp = cat_fp_x(x1, x2);
267 1 RETVAL = newSVpvn(ll2x16(fp), 16);
268 OUTPUT:
269 RETVAL
270  
271 SV *ll2x(fp)
272 long fp;
273 CODE:
274 0 RETVAL = newSVpvn(ll2x16(fp), 16);
275 OUTPUT:
276 RETVAL
277  
278 long x2l(x)
279 const char *x
280 CODE:
281 0 ▶ RETVAL = x2i64((unsigned char *)x, strlen(x));
Branch: 1 branch
BranchTrueFalseTotal
RETVAL = x2i64((unsigned char *)x, strlen(x)); 0 0 0
282 OUTPUT:
283 RETVAL
284  
285 SV*
286 cooked(sv_text, ...)
287 SV *sv_text
288 INIT:
289 STRLEN text_len; // like strlen(text), but including '\0' bytes. STRLEN is unsigned!
290 IV start_off;
291 IV len;
292 const char *text;
293 char *cooked_text;
294 int cooked_len;
295  
296 SV *text_out;
297  
298 0 text = (const char *)SvPV(sv_text, text_len);
299 0 ▶ if ( items > 1)
Branch: 1 branch
BranchTrueFalseTotal
if ( items > 1) 0 0 0
300 {
301 0 start_off = SvIV(ST(1));
302 0 ▶ if (start_off > text_len)
Branch: 1 branch
BranchTrueFalseTotal
if (start_off > text_len) 0 0 0
303 0 croak("specified offset=%d is beyond text_len=%d",
304 (int)start_off, (int)text_len);
305 0 text_len -= start_off;
306 }
307 else
308 0 start_off = 0;
309  
310 0 ▶ if ( items > 2)
Branch: 1 branch
BranchTrueFalseTotal
if ( items > 2) 0 0 0
311 {
312 0 len = SvIV(ST(2));
313 0 ▶ if (len > text_len)
Branch: 1 branch
BranchTrueFalseTotal
if (len > text_len) 0 0 0
314 0 croak("specified length=%d exceeds text_len=%d", (int)len, (int)text_len);
315 0 text_len = len;
316 }
317  
318 CODE:
319 0 cooked_text = (char *)malloc(text_len); // never longer than raw text;
320 0 cooked_len = cook_text(cooked_text, text+start_off, text_len);
321  
322 // transfer output from C to perl
323 0 text_out = newSVpvn(cooked_text, cooked_len);
324  
325 // forget C
326 0 free((char *)cooked_text);
327 // do not free text, it points into perl proper.
328 // (Would cause an abort in PerlIOBuf_close)
329  
330 0 RETVAL = text_out;
331 OUTPUT:
332 RETVAL
333  
« blib/lib/Digest/mkrandomtable.pl ↑ Summary blib/lib/Digest/FP56x1xor.pm »