File Coverage

SpeedyFx.xs
Criterion Covered Total %
statement 155 167 92.8
branch 163 258 63.1
condition n/a
subroutine n/a
pod n/a
total 318 425 74.8


line stmt bran cond sub pod time code
1             #include "EXTERN.h"
2             #include "perl.h"
3             #include "XSUB.h"
4              
5             #include "ppport.h"
6              
7             #include "nedtrie.h"
8              
9             #define MAX_MAP_SIZE 0x2ffff
10             #define SFX_SIGNATURE 0x4c9da21d
11              
12             #ifndef MAX_TRIE_SIZE
13             #define MAX_TRIE_SIZE (1 << 19)
14             #endif
15              
16             typedef struct {
17             U32 length;
18             U32 code_table[];
19             } SpeedyFx;
20             typedef SpeedyFx *Text__SpeedyFx;
21              
22             typedef struct sfxaa_s sfxaa_t;
23             struct sfxaa_s {
24             NEDTRIE_ENTRY(sfxaa_s) link;
25             U32 key;
26             U32 val;
27             };
28             typedef struct sfxaa_tree_s sfxaa_tree_t;
29             NEDTRIE_HEAD(sfxaa_tree_s, sfxaa_s);
30              
31 1175           U32 sfxaakeyfunct(const sfxaa_t *r) {
32 1175           return r->key;
33             }
34              
35 2105 100         NEDTRIE_GENERATE(static, sfxaa_tree_s, sfxaa_s, link, sfxaakeyfunct, NEDTRIE_NOBBLEONES(sfxaa_tree_s))
    100          
    100          
    100          
    50          
    50          
    100          
    100          
    100          
    100          
    100          
    100          
    50          
    50          
    100          
    0          
    0          
    0          
    0          
    0          
    100          
    100          
    100          
    100          
    50          
    50          
    0          
    50          
    50          
    50          
    50          
    0          
    100          
    100          
    50          
    50          
    50          
    100          
    50          
    0          
    100          
36              
37             typedef struct {
38             U32 signature;
39             U32 count;
40             sfxaa_tree_t root;
41             sfxaa_t *last;
42             sfxaa_t index[MAX_TRIE_SIZE];
43             } SpeedyFxResult;
44             typedef SpeedyFxResult *Text__SpeedyFx__Result;
45              
46 3           SV *result_init () {
47             SV *res;
48             int count;
49              
50 3           dSP;
51 3           ENTER;
52 3           SAVETMPS;
53              
54 3 50         PUSHMARK(SP);
55 3 50         XPUSHs(sv_2mortal(newSVpv("Text::SpeedyFx::Result", 0)));
56 3           PUTBACK;
57              
58 3           count = call_method("new", G_SCALAR);
59 3           SPAGAIN;
60              
61 3 50         if (count != 1)
62 0           croak("couldn't construct new Text::SpeedyFx::Result object");
63              
64 3           res = newSVsv(POPs);
65              
66 3           PUTBACK;
67 3 50         FREETMPS;
68 3           LEAVE;
69              
70 3           return res;
71             }
72              
73 3           SpeedyFxResult *result_addr (SV *self) {
74             SV *hash;
75             MAGIC *magic;
76             SV *attr;
77 3           SpeedyFxResult *pSpeedyFxResult = NULL;
78              
79 3           hash = SvRV(self);
80 3 50         if (SvRMAGICAL((SV *) hash)) {
81 3 50         if ((magic = mg_find((SV *) hash, PERL_MAGIC_tied)) != NULL) {
82 3           attr = magic->mg_obj;
83 3 50         if (SvROK(attr)) {
84 3 50         pSpeedyFxResult = (SpeedyFxResult *) SvIV(SvRV(attr));
85 3 50         if (pSpeedyFxResult->signature != SFX_SIGNATURE) {
86 0           pSpeedyFxResult = NULL;
87             }
88             }
89             }
90             }
91              
92 3           return pSpeedyFxResult;
93             }
94              
95             #if PERL_VERSION >= 16
96             #define ChrCode(u, v, len) (U32) utf8_to_uvchr_buf(u, v, len)
97             #else
98             #define ChrCode(u, v, len) (U32) utf8_to_uvchr(u, len)
99             #endif
100              
101             #if PERL_VERSION >= 32
102             #define ChrIsAlphanum(s, end) isWORDCHAR_utf8_safe(s, end)
103             #define ChrToLower(p, e, s, lenp) toLOWER_utf8_safe(p, e, s, lenp)
104             #else
105             #define ChrIsAlphanum(s, end) isALNUM_utf8(s)
106             #define ChrToLower(p, e, s, lenp) toLOWER_utf8(p, s, lenp)
107             #endif
108              
109             #define SetBit(a, b) (((U8 *) a)[(b) >> 3] |= (1 << ((b) & 7)))
110             #define FastMin(x, y) (y ^ ((x ^ y) & -(x < y)))
111              
112             #define _SPEEDYFX_INIT \
113             U32 code, c; \
114             U32 wordhash = 0; \
115             STRLEN len; \
116             U32 length = pSpeedyFx->length; \
117             U32 *code_table = pSpeedyFx->code_table; \
118             U8 *s, *se; \
119             s = (U8 *) SvPV(str, len); \
120             se = s + len;
121              
122             #define _WALK_LATIN1 c = *s++
123             #define _WALK_UTF8 c = ChrCode(s, se, &len); s += len
124              
125             #define _SPEEDYFX(_STORE, _WALK, _LENGTH) \
126             STMT_START { \
127             while (*s) { \
128             _WALK; \
129             if ((code = code_table[c % _LENGTH]) != 0) \
130             wordhash = (wordhash >> 1) + code; \
131             else if (wordhash) { \
132             _STORE; \
133             wordhash = 0; \
134             } \
135             } \
136             if (wordhash) { \
137             _STORE; \
138             } \
139             } STMT_END
140              
141             #define _NEDTRIE_STORE \
142             tmp.key = wordhash; \
143             if ((p = NEDTRIE_FIND(sfxaa_tree_s, root, &tmp)) != 0) \
144             p->val++; \
145             else { \
146             if ((p = slot++) == end) \
147             croak("too many unique tokens in a single data chunk"); \
148             p->key = wordhash; \
149             p->val = 1; \
150             NEDTRIE_INSERT(sfxaa_tree_s, root, p); \
151             }
152              
153             MODULE = Text::SpeedyFx::Result PACKAGE = Text::SpeedyFx::Result
154              
155             PROTOTYPES: ENABLE
156              
157             SV *
158             new (package, ...)
159             char *package;
160             PREINIT:
161             SpeedyFxResult *pSpeedyFxResult;
162             HV *thingy;
163             HV *stash;
164             SV *tie;
165             CODE:
166 4           Newx(pSpeedyFxResult, 1, SpeedyFxResult);
167 4           pSpeedyFxResult->signature = SFX_SIGNATURE;
168 4           pSpeedyFxResult->count = 0;
169              
170 4           NEDTRIE_INIT(&(pSpeedyFxResult->root));
171              
172 4           thingy = newHV();
173 4           tie = newRV_noinc(newSViv(PTR2IV(pSpeedyFxResult)));
174 4           stash = gv_stashpv(package, GV_ADD);
175 4           sv_bless(tie, stash);
176 4           hv_magic(thingy, (GV *) tie, PERL_MAGIC_tied);
177 4           sv_free(tie);
178              
179 4           RETVAL = newRV_noinc((SV *) thingy);
180             OUTPUT:
181             RETVAL
182              
183             void
184             FETCH (pSpeedyFxResult, key)
185             Text::SpeedyFx::Result pSpeedyFxResult
186             SV *key
187             INIT:
188             sfxaa_t *p, tmp;
189             PPCODE:
190 105 100         tmp.key = SvNV(key);
191 105 100         if ((p = NEDTRIE_FIND(sfxaa_tree_s, &(pSpeedyFxResult->root), &tmp)) == 0) {
192 1           XSRETURN_UNDEF;
193             } else {
194 104           ST(0) = sv_2mortal(newSVnv(p->val));
195 105           XSRETURN(1);
196             }
197              
198             void
199             STORE (pSpeedyFxResult, key, value)
200             Text::SpeedyFx::Result pSpeedyFxResult
201             SV *key
202             SV *value
203             INIT:
204             sfxaa_t *p, tmp;
205             PPCODE:
206 40 50         tmp.key = SvNV(key);
207 40 50         tmp.val = SvNV(value);
208 40 50         if ((p = NEDTRIE_FIND(sfxaa_tree_s, &(pSpeedyFxResult->root), &tmp)) != 0)
209 0           p->val = tmp.val;
210             else {
211 40 50         if (pSpeedyFxResult->count++ >= MAX_TRIE_SIZE)
212 0           croak("too many unique tokens in a single data chunk");
213 40           p = &(pSpeedyFxResult->index[pSpeedyFxResult->count]);
214 40           p->key = tmp.key;
215 40           p->val = tmp.val;
216 40           NEDTRIE_INSERT(sfxaa_tree_s, &(pSpeedyFxResult->root), p);
217             }
218              
219             void
220             DELETE (pSpeedyFxResult, key)
221             Text::SpeedyFx::Result pSpeedyFxResult
222             SV *key
223             INIT:
224             sfxaa_t *p, tmp;
225             PPCODE:
226 2 50         tmp.key = SvNV(key);
227 2 100         if ((p = NEDTRIE_FIND(sfxaa_tree_s, &(pSpeedyFxResult->root), &tmp)) == 0) {
228 1           XSRETURN_UNDEF;
229             } else {
230 1           ST(0) = sv_2mortal(newSVnv(p->val));
231 1           NEDTRIE_REMOVE(sfxaa_tree_s, &(pSpeedyFxResult->root), p);
232 2           XSRETURN(1);
233             }
234              
235             void
236             CLEAR (pSpeedyFxResult)
237             Text::SpeedyFx::Result pSpeedyFxResult
238             PPCODE:
239 1           NEDTRIE_INIT(&(pSpeedyFxResult->root));
240 1           pSpeedyFxResult->count = 0;
241              
242             void
243             EXISTS (pSpeedyFxResult, key)
244             Text::SpeedyFx::Result pSpeedyFxResult
245             SV *key
246             INIT:
247             sfxaa_t *p, tmp;
248             PPCODE:
249 42 100         tmp.key = SvNV(key);
250 42 100         if ((p = NEDTRIE_FIND(sfxaa_tree_s, &(pSpeedyFxResult->root), &tmp)) == 0) {
251 1           XSRETURN_NO;
252             } else {
253 42           XSRETURN_YES;
254             }
255              
256             void
257             FIRSTKEY (pSpeedyFxResult)
258             Text::SpeedyFx::Result pSpeedyFxResult
259             INIT:
260             sfxaa_t *p;
261             PPCODE:
262 7 100         if ((p = NEDTRIE_MIN(sfxaa_tree_s, &(pSpeedyFxResult->root))) == 0) {
263 1           XSRETURN_UNDEF;
264             } else {
265 6           pSpeedyFxResult->last = p;
266              
267 6           ST(0) = sv_2mortal(newSVnv(p->key));
268 6           XSRETURN(1);
269             }
270              
271             void
272             NEXTKEY (pSpeedyFxResult, ...)
273             Text::SpeedyFx::Result pSpeedyFxResult
274             INIT:
275             sfxaa_t *p;
276             PPCODE:
277 120 100         if ((p = NEDTRIE_NEXT(sfxaa_tree_s, &(pSpeedyFxResult->root), pSpeedyFxResult->last)) == 0) {
278 5           XSRETURN_UNDEF;
279             } else {
280 115           pSpeedyFxResult->last = p;
281              
282 115           ST(0) = sv_2mortal(newSVnv(p->key));
283 115           XSRETURN(1);
284             }
285              
286             void
287             SCALAR (pSpeedyFxResult)
288             Text::SpeedyFx::Result pSpeedyFxResult
289             PPCODE:
290 2           ST(0) = sv_2mortal(newSVpvf("%d/%d", pSpeedyFxResult->count, MAX_TRIE_SIZE));
291 2           XSRETURN(1);
292              
293             void
294             UNTIE (...)
295             PPCODE:
296 0           croak("not implemented");
297              
298             void
299             DESTROY (pSpeedyFxResult)
300             Text::SpeedyFx::Result pSpeedyFxResult
301             PPCODE:
302 4           Safefree(pSpeedyFxResult);
303              
304             MODULE = Text::SpeedyFx PACKAGE = Text::SpeedyFx
305              
306             PROTOTYPES: ENABLE
307              
308             Text::SpeedyFx
309             new (...)
310             PREINIT:
311 4           U32 seed = 1;
312 4           U8 bits = 18;
313             static U32 fold_init = 0;
314             static U32 fold_table[MAX_MAP_SIZE];
315             INIT:
316             U32 i;
317             U8 s[8];
318             U8 *t;
319             U8 u[8], *v;
320             UV c;
321             STRLEN len;
322             U32 length, *code_table;
323             U32 rand_table[MAX_MAP_SIZE];
324             CODE:
325 4 50         if (items > 1)
326 4 50         seed = SvNV(ST(1));
327 4 100         if (items > 2)
328 2 50         bits = SvNV(ST(2));
329              
330 4 100         if (seed == 0)
331 1           croak("seed must be not 0!");
332              
333 3 100         if (bits <= 8)
334 2           length = 256;
335 1 50         else if (bits > 17)
336 1           length = MAX_MAP_SIZE;
337             else
338 0           length = 1 << bits;
339              
340             SpeedyFx *pSpeedyFx;
341 3 50         Newxc(pSpeedyFx, 1 + length, U32, SpeedyFx);
342              
343 3           pSpeedyFx->length = length;
344 3           code_table = pSpeedyFx->code_table;
345              
346 3           fold_table[0] = 0;
347 3 50         if (fold_init < length) {
348 197119 100         for (i = fold_init + 1; i < length; i++) {
349 197116 100         if (i >= 0xd800 && i <= 0xdfff) // high/low-surrogate code points
    100          
350 2048           c = 0;
351 195068 100         else if (i >= 0xfdd0 && i <= 0xfdef) // noncharacters
    100          
352 32           c = 0;
353 195036 100         else if ((i & 0xffff) == 0xfffe) // noncharacters
354 3           c = 0;
355 195033 100         else if ((i & 0xffff) == 0xffff) // noncharacters
356 2           c = 0;
357             else {
358 195031           t = uvchr_to_utf8(s, (UV) i);
359 195031           *t = '\0';
360              
361 195031 100         if (ChrIsAlphanum(s, t)) {
362 119837           (void) ChrToLower(s, t, u, &len);
363 119837           *(u + len) = '\0';
364 119837           v = u + len;
365              
366 119837 50         c = ChrCode(u, v, &len);
367              
368             // grow the tables, if necessary
369 119837 50         if (length < c)
370 119837           length = c;
371             } else
372 75194           c = 0;
373             }
374 197116           fold_table[i] = c;
375             }
376 3           fold_init = length;
377             }
378              
379 3 50         if (pSpeedyFx->length != length) {
380 0 0         Renewc(pSpeedyFx, 1 + length, U32, SpeedyFx);
381              
382 0           pSpeedyFx->length = length;
383 0           code_table = pSpeedyFx->code_table;
384             }
385 3 50         Zero(code_table, length, U32);
386              
387 3           rand_table[0] = seed;
388 197119 100         for (i = 1; i < length; i++)
389             rand_table[i]
390 197116           = (
391 197116           rand_table[i - 1]
392 197116           * 0x10a860c1
393 197116           ) % 0xfffffffb;
394              
395 197122 100         for (i = 0; i < length; i++)
396 197119 100         if (fold_table[i])
397 119837           code_table[i] = rand_table[fold_table[i]];
398              
399 3           RETVAL = pSpeedyFx;
400             OUTPUT:
401             RETVAL
402              
403             void
404             hash (pSpeedyFx, str)
405             Text::SpeedyFx pSpeedyFx
406             SV *str
407             INIT:
408 3 50         _SPEEDYFX_INIT;
409             SV *res;
410             SpeedyFxResult *pSpeedyFxResult;
411             sfxaa_tree_t *root;
412             sfxaa_t *p, *slot, *end, tmp;
413             PPCODE:
414 3           res = result_init();
415 3 50         if ((pSpeedyFxResult = result_addr(res)) == NULL)
416 0           croak("TARFU");
417              
418 3           root = &(pSpeedyFxResult->root);
419 3           slot = &(pSpeedyFxResult->index[0]);
420 3           end = &(pSpeedyFxResult->index[MAX_TRIE_SIZE]);
421              
422 3 100         if (length > 256) {
423 270 50         _SPEEDYFX(_NEDTRIE_STORE, _WALK_UTF8, length);
    100          
    100          
    100          
    50          
    100          
    50          
    0          
    0          
424             } else {
425 289 100         _SPEEDYFX(_NEDTRIE_STORE, _WALK_LATIN1, 256);
    100          
    100          
    50          
    100          
    50          
    0          
    0          
426             }
427              
428 3           pSpeedyFxResult->count = (slot - pSpeedyFxResult->index) / sizeof(sfxaa_t);
429              
430 3           ST(0) = sv_2mortal(res);
431 3           XSRETURN(1);
432              
433             void
434             DESTROY (pSpeedyFx)
435             Text::SpeedyFx pSpeedyFx
436             PPCODE:
437 3           Safefree(pSpeedyFx);
438 3           XSRETURN(0);
439              
440             void
441             hash_fv (pSpeedyFx, str, n)
442             Text::SpeedyFx pSpeedyFx
443             SV *str
444             U32 n
445             INIT:
446 1 50         _SPEEDYFX_INIT;
447 1           U32 size = ceil((float) n / 8.0);
448             char *fv;
449             PPCODE:
450 1           Newxz(fv, size, char);
451              
452 1 50         if (length > 256) {
453 270 50         _SPEEDYFX(SetBit(fv, wordhash % n), _WALK_UTF8, length);
    100          
    100          
    100          
    50          
454             } else {
455 0 0         _SPEEDYFX(SetBit(fv, wordhash % n), _WALK_LATIN1, 256);
    0          
    0          
    0          
456             }
457              
458 1           ST(0) = sv_2mortal(newSVpv(fv, size));
459 1           Safefree(fv);
460 1           XSRETURN(1);
461              
462             void
463             hash_min (pSpeedyFx, str)
464             Text::SpeedyFx pSpeedyFx
465             SV *str
466             INIT:
467 1 50         _SPEEDYFX_INIT;
468 1           U32 min = 0xffffffff;
469             PPCODE:
470 1 50         if (length > 256) {
471 270 50         _SPEEDYFX(min = FastMin(min, wordhash), _WALK_UTF8, length);
    100          
    100          
    100          
    50          
472             } else {
473 0 0         _SPEEDYFX(min = FastMin(min, wordhash), _WALK_LATIN1, 256);
    0          
    0          
    0          
474             }
475              
476 1           ST(0) = sv_2mortal(newSVnv(min));
477 1           XSRETURN(1);