ushufflelib/ushuffle.c

filter: Statementstmt 91.7% 122 / 133 Branchbran 96.3% 52 / 54 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.0% 174 / 187 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« Ushuffle.xs ↑ Summary blib/lib/Ushuffle.pm »
1 /* Copyright (c) 2007
2 * Minghui Jiang, James Anderson, Joel Gillespie, and Martin Mayne.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * 1. Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright notice,
10 * this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * 3. The names of its contributors may not be used to endorse or promote
13 * products derived from this software without specific prior written
14 * permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
20 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28  
29 /*
30 * ushuffle.c - uShuffle library code
31 * Mon Apr 23 14:35:21 MDT 2007
32 */
33  
34 #include <ctype.h>
35 #include <math.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include "ushuffle.h"
40  
41 /* set random function */
42  
43 static randfunc_t randfunc = random;
44  
45 0 void set_randfunc(randfunc_t func) {
46 0 randfunc = func;
47 0 }
48  
49 /* global variables for the Euler algorithm */
50  
51 static char *s_ = NULL;
52 static int l_ = 0;
53 static int k_ = 0;
54  
55 typedef struct vertex {
56 int *indices;
57 int n_indices;
58 int i_indices;
59 int intree, next;
60 int i_sequence;
61 } vertex;
62  
63 static vertex *vertices = NULL;
64 static int n_vertices;
65 static int *indices = NULL;
66 static int root;
67  
68 /* memory utility */
69  
70 474364 static void *malloc0(size_t size) {
71 void *mem;
72  
73 474364 ▶ if ((mem = malloc(size)) == NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if ((mem = malloc(size)) == NULL) { 0 474364 474364
74 0 fprintf(stderr, "malloc0: malloc failed\n");
75 0 exit(1);
76 }
77 474364 return memset(mem, 0, size);
78 }
79  
80 /* hashtable utility */
81  
82 typedef struct hentry {
83 struct hentry *next;
84 int i_sequence;
85 int i_vertices;
86 } hentry;
87  
88 static hentry *entries = NULL;
89 static hentry **htable = NULL;
90 static int htablesize = 0;
91 static double hmagic;
92  
93 29017737 static int hcode(int i_sequence) {
94 29017737 double f = 0.0;
95 int i;
96  
97 163094494 ▶ for (i = 0; i < k_ - 1; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < k_ - 1; i++) { 134076757 29017737 163094494
98 134076757 f += s_[i_sequence + i];
99 134076757 f *= hmagic;
100 }
101 29017737 ▶ if (f < 0.0)
Branch: 1 branch
BranchTrueFalseTotal
if (f < 0.0) 58273 28959464 29017737
102 58273 f = -f;
103 29017737 return (int) ((long long) (htablesize * f) % htablesize);
104 }
105  
106 118591 static void hinit(int size) {
107 118591 entries = malloc0(size * sizeof(hentry));
108 118591 htable = malloc0(size * sizeof(hentry *));
109 118591 htablesize = size;
110 118591 hmagic = (sqrt(5.0) - 1.0) / 2.0;
111 118591 }
112  
113 118591 static void hcleanup() {
114 118591 free(entries);
115 118591 entries = NULL;
116 118591 free(htable);
117 118591 htable = NULL;
118 118591 htablesize = 0;
119 118591 }
120  
121 29017737 static void hinsert(int i_sequence) {
122 29017737 int code = hcode(i_sequence);
123 29017737 hentry *e, *e2 = &entries[i_sequence];
124  
125 191788596 ▶ for (e = htable[code]; e; e = e->next)
Branch: 1 branch
BranchTrueFalseTotal
for (e = htable[code]; e; e = e->next) 190965846 822750 191788596
126 190965846 ▶ if (strncmp(&s_[e->i_sequence], &s_[i_sequence], k_ - 1) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (strncmp(&s_[e->i_sequence], &s_[i_sequence], k_ - 1) == 0) { 28194987 162770859 190965846
127 28194987 e2->i_sequence = e->i_sequence;
128 28194987 e2->i_vertices = e->i_vertices;
129 28194987 return;
130 }
131 822750 e2->i_sequence = i_sequence;
132 822750 e2->i_vertices = n_vertices++;
133 822750 e2->next = htable[code];
134 822750 htable[code] = e2;
135 }
136  
137 /* the Euler algorithm */
138 163775 void shuffle1(const char *s, int l, int k) {
139 int i, j, n_lets;
140  
141 163775 ▶ if (s_)
Branch: 1 branch
BranchTrueFalseTotal
if (s_) 163759 16 163775
142 163759 free (s_);
143 163775 ▶ if ((s_ = malloc(l * sizeof(char))) == NULL) {
Branch: 1 branch
BranchTrueFalseTotal
if ((s_ = malloc(l * sizeof(char))) == NULL) { 0 163775 163775
144 0 fprintf(stderr, "shuffle1: malloc failed\n");
145 0 exit(1);
146 }
147 163775 strncpy(s_, s, l);
148 163775 l_ = l;
149 163775 k_ = k;
150 163775 ▶ if (k_ >= l_ || k_ <= 1) /* two special cases */
Branch: 2 branches
BranchTrueFalseTotal
if (k_ >= l_ || k_ <= 1) /* two special cases */ 163557 218 163775
if (k_ >= l_ || k_ <= 1) /* two special cases */ 44966 118591 163557
151 45184 return;
152  
153 /* use hashtable to find distinct vertices */
154 118591 n_lets = l_ - k_ + 2; /* number of (k-1)-lets */
155 118591 n_vertices = 0;
156 118591 hinit(n_lets);
157 29136328 ▶ for (i = 0; i < n_lets; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_lets; i++) 29017737 118591 29136328
158 29017737 hinsert(i);
159 118591 root = entries[n_lets - 1].i_vertices; /* the last let */
160 118591 ▶ if (vertices)
Branch: 1 branch
BranchTrueFalseTotal
if (vertices) 118575 16 118591
161 118575 free(vertices);
162 118591 vertices = malloc0(n_vertices * sizeof(vertex));
163  
164 /* set i_sequence and n_indices for each vertex */
165 29136328 ▶ for (i = 0; i < n_lets; i++) { /* for each let */
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_lets; i++) { /* for each let */ 29017737 118591 29136328
166 29017737 hentry *ev = &entries[i];
167 29017737 vertex *v = &vertices[ev->i_vertices];
168  
169 29017737 v->i_sequence = ev->i_sequence;
170 29017737 ▶ if (i < n_lets - 1) /* not the last let */
Branch: 1 branch
BranchTrueFalseTotal
if (i < n_lets - 1) /* not the last let */ 28899146 118591 29017737
171 28899146 v->n_indices++;
172 }
173  
174 /* distribute indices for each vertex */
175 118591 ▶ if (indices)
Branch: 1 branch
BranchTrueFalseTotal
if (indices) 118575 16 118591
176 118575 free(indices);
177 118591 indices = malloc0((n_lets - 1) * sizeof(int));
178 118591 j = 0;
179 941341 ▶ for (i = 0; i < n_vertices; i++) { /* for each vertex */
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_vertices; i++) { /* for each vertex */ 822750 118591 941341
180 822750 vertex *v = &vertices[i];
181  
182 822750 v->indices = indices + j;
183 822750 j += v->n_indices;
184 }
185  
186 /* populate indices for each vertex */
187 29017737 ▶ for (i = 0; i < n_lets - 1; i++) { /* for each edge */
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_lets - 1; i++) { /* for each edge */ 28899146 118591 29017737
188 28899146 hentry *eu = &entries[i];
189 28899146 hentry *ev = &entries[i + 1];
190 28899146 vertex *u = &vertices[eu->i_vertices];
191  
192 28899146 u->indices[u->i_indices++] = ev->i_vertices;
193 }
194 118591 hcleanup();
195 }
196  
197 88497 void permutec(char *t, int l) {
198 int i, j;
199 char tmp;
200  
201 941846 ▶ for (i = l - 1; i > 0; i--) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = l - 1; i > 0; i--) { 853349 88497 941846
202 853349 j = (*randfunc)() % (i + 1);
203 853349 tmp = t[i]; t[i] = t[j]; t[j] = tmp; /* swap */
204 }
205 88497 }
206  
207 1204113 static void permutei(int *t, int l) {
208 int i, j;
209 int tmp;
210  
211 29816169 ▶ for (i = l - 1; i > 0; i--) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = l - 1; i > 0; i--) { 28612056 1204113 29816169
212 28612056 j = (*randfunc)() % (i + 1);
213 28612056 tmp = t[i]; t[i] = t[j]; t[j] = tmp; /* swap */
214 }
215 1204113 }
216  
217 283006 void shuffle2(char *t) {
218 vertex *u, *v;
219 int i, j;
220  
221 /* exact copy case */
222 283006 ▶ if (k_ >= l_) {
Branch: 1 branch
BranchTrueFalseTotal
if (k_ >= l_) { 260 282746 283006
223 260 strncpy(t, s_, l_);
224 260 return;
225 }
226  
227 /* simple permutation case */
228 282746 ▶ if (k_ <= 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (k_ <= 1) { 88497 194249 282746
229 88497 strncpy(t, s_, l_);
230 88497 permutec(t, l_);
231 88497 return;
232 }
233  
234 /* the Wilson algorithm for random arborescence */
235 1398362 ▶ for (i = 0; i < n_vertices; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_vertices; i++) 1204113 194249 1398362
236 1204113 vertices[i].intree = 0;
237 194249 vertices[root].intree = 1;
238 1398362 ▶ for (i = 0; i < n_vertices; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_vertices; i++) { 1204113 194249 1398362
239 1204113 u = &vertices[i];
240 2542478 ▶ while (!u->intree) {
Branch: 1 branch
BranchTrueFalseTotal
while (!u->intree) { 1338365 1204113 2542478
241 1338365 u->next = (*randfunc)() % u->n_indices;
242 1338365 u = &vertices[u->indices[u->next]];
243 }
244 1204113 u = &vertices[i];
245 2213977 ▶ while (!u->intree) {
Branch: 1 branch
BranchTrueFalseTotal
while (!u->intree) { 1009864 1204113 2213977
246 1009864 u->intree = 1;
247 1009864 u = &vertices[u->indices[u->next]];
248 }
249 }
250  
251 /* shuffle indices to prepare for walk */
252 1398362 ▶ for (i = 0; i < n_vertices; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n_vertices; i++) { 1204113 194249 1398362
253 1204113 u = &vertices[i];
254 1204113 ▶ if (i != root) {
Branch: 1 branch
BranchTrueFalseTotal
if (i != root) { 1009864 194249 1204113
255 1009864 j = u->indices[u->n_indices - 1]; /* swap the last one */
256 1009864 u->indices[u->n_indices - 1] = u->indices[u->next];
257 1009864 u->indices[u->next] = j;
258 1009864 permutei(u->indices, u->n_indices - 1); /* permute the rest */
259 } else
260 194249 permutei(u->indices, u->n_indices);
261 1204113 u->i_indices = 0; /* reset to zero before walk */
262 }
263  
264 /* walk the graph */
265 194249 strncpy(t, s_, k_ - 1); /* the first let remains the same */
266 194249 u = &vertices[0];
267 194249 i = k_ - 1;
268 30583532 ▶ while (u->i_indices < u->n_indices) {
Branch: 1 branch
BranchTrueFalseTotal
while (u->i_indices < u->n_indices) { 30389283 194249 30583532
269 30389283 v = &vertices[u->indices[u->i_indices]];
270 30389283 j = v->i_sequence + k_ - 2;
271 30389283 t[i++] = s_[j];
272 30389283 u->i_indices++;
273 30389283 u = v;
274 }
275 }
276  
277 0 void shuffle(const char *s, char *t, int l, int k) {
278 0 shuffle1(s, l, k);
279 0 shuffle2(t);
280 0 }
« Ushuffle.xs ↑ Summary blib/lib/Ushuffle.pm »