| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (s_) |
163759 |
16 |
163775 |
|
| 142 |
163759 |
| free (s_); |
| 143 |
163775 |
▶ | if ((s_ = malloc(l * sizeof(char))) == NULL) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n_vertices; i++) { |
1204113 |
194249 |
1398362 |
|
| 239 |
1204113 |
| u = &vertices[i]; |
| 240 |
2542478 |
▶ | while (!u->intree) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n_vertices; i++) { |
1204113 |
194249 |
1398362 |
|
| 253 |
1204113 |
| u = &vertices[i]; |
| 254 |
1204113 |
▶ | if (i != root) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
| } |