4efb3868 |
1 | /* |
2 | * misc.c: Miscellaneous helpful functions. |
3 | */ |
4 | |
5 | #include <assert.h> |
6 | #include <stdlib.h> |
74476385 |
7 | #include <string.h> |
8 | #include <stdio.h> |
4efb3868 |
9 | |
10 | #include "puzzles.h" |
11 | |
077f3cbe |
12 | void free_cfg(config_item *cfg) |
13 | { |
14 | config_item *i; |
15 | |
16 | for (i = cfg; i->type != C_END; i++) |
17 | if (i->type == C_STRING) |
18 | sfree(i->sval); |
19 | sfree(cfg); |
20 | } |
74476385 |
21 | |
22 | /* |
23 | * The Mines (among others) game descriptions contain the location of every |
24 | * mine, and can therefore be used to cheat. |
25 | * |
26 | * It would be pointless to attempt to _prevent_ this form of |
27 | * cheating by encrypting the description, since Mines is |
28 | * open-source so anyone can find out the encryption key. However, |
29 | * I think it is worth doing a bit of gentle obfuscation to prevent |
30 | * _accidental_ spoilers: if you happened to note that the game ID |
31 | * starts with an F, for example, you might be unable to put the |
32 | * knowledge of those mines out of your mind while playing. So, |
33 | * just as discussions of film endings are rot13ed to avoid |
34 | * spoiling it for people who don't want to be told, we apply a |
35 | * keyless, reversible, but visually completely obfuscatory masking |
36 | * function to the mine bitmap. |
37 | */ |
38 | void obfuscate_bitmap(unsigned char *bmp, int bits, int decode) |
39 | { |
40 | int bytes, firsthalf, secondhalf; |
41 | struct step { |
42 | unsigned char *seedstart; |
43 | int seedlen; |
44 | unsigned char *targetstart; |
45 | int targetlen; |
46 | } steps[2]; |
47 | int i, j; |
48 | |
49 | /* |
50 | * My obfuscation algorithm is similar in concept to the OAEP |
51 | * encoding used in some forms of RSA. Here's a specification |
52 | * of it: |
53 | * |
54 | * + We have a `masking function' which constructs a stream of |
55 | * pseudorandom bytes from a seed of some number of input |
56 | * bytes. |
57 | * |
58 | * + We pad out our input bit stream to a whole number of |
59 | * bytes by adding up to 7 zero bits on the end. (In fact |
60 | * the bitmap passed as input to this function will already |
61 | * have had this done in practice.) |
62 | * |
63 | * + We divide the _byte_ stream exactly in half, rounding the |
64 | * half-way position _down_. So an 81-bit input string, for |
65 | * example, rounds up to 88 bits or 11 bytes, and then |
66 | * dividing by two gives 5 bytes in the first half and 6 in |
67 | * the second half. |
68 | * |
69 | * + We generate a mask from the second half of the bytes, and |
70 | * XOR it over the first half. |
71 | * |
72 | * + We generate a mask from the (encoded) first half of the |
73 | * bytes, and XOR it over the second half. Any null bits at |
74 | * the end which were added as padding are cleared back to |
75 | * zero even if this operation would have made them nonzero. |
76 | * |
77 | * To de-obfuscate, the steps are precisely the same except |
78 | * that the final two are reversed. |
79 | * |
80 | * Finally, our masking function. Given an input seed string of |
81 | * bytes, the output mask consists of concatenating the SHA-1 |
82 | * hashes of the seed string and successive decimal integers, |
83 | * starting from 0. |
84 | */ |
85 | |
86 | bytes = (bits + 7) / 8; |
87 | firsthalf = bytes / 2; |
88 | secondhalf = bytes - firsthalf; |
89 | |
90 | steps[decode ? 1 : 0].seedstart = bmp + firsthalf; |
91 | steps[decode ? 1 : 0].seedlen = secondhalf; |
92 | steps[decode ? 1 : 0].targetstart = bmp; |
93 | steps[decode ? 1 : 0].targetlen = firsthalf; |
94 | |
95 | steps[decode ? 0 : 1].seedstart = bmp; |
96 | steps[decode ? 0 : 1].seedlen = firsthalf; |
97 | steps[decode ? 0 : 1].targetstart = bmp + firsthalf; |
98 | steps[decode ? 0 : 1].targetlen = secondhalf; |
99 | |
100 | for (i = 0; i < 2; i++) { |
101 | SHA_State base, final; |
102 | unsigned char digest[20]; |
103 | char numberbuf[80]; |
104 | int digestpos = 20, counter = 0; |
105 | |
106 | SHA_Init(&base); |
107 | SHA_Bytes(&base, steps[i].seedstart, steps[i].seedlen); |
108 | |
109 | for (j = 0; j < steps[i].targetlen; j++) { |
110 | if (digestpos >= 20) { |
111 | sprintf(numberbuf, "%d", counter++); |
112 | final = base; |
113 | SHA_Bytes(&final, numberbuf, strlen(numberbuf)); |
114 | SHA_Final(&final, digest); |
115 | digestpos = 0; |
116 | } |
117 | steps[i].targetstart[j] ^= digest[digestpos++]; |
118 | } |
119 | |
120 | /* |
121 | * Mask off the pad bits in the final byte after both steps. |
122 | */ |
123 | if (bits % 8) |
124 | bmp[bits / 8] &= 0xFF & (0xFF00 >> (bits % 8)); |
125 | } |
126 | } |
127 | |
128 | /* err, yeah, these two pretty much rely on unsigned char being 8 bits. |
129 | * Platforms where this is not the case probably have bigger problems |
130 | * than just making these two work, though... */ |
131 | char *bin2hex(const unsigned char *in, int inlen) |
132 | { |
133 | char *ret = snewn(inlen*2 + 1, char), *p = ret; |
134 | int i; |
135 | |
136 | for (i = 0; i < inlen*2; i++) { |
137 | int v = in[i/2]; |
138 | if (i % 2 == 0) v >>= 4; |
139 | *p++ = "0123456789abcdef"[v & 0xF]; |
140 | } |
141 | *p = '\0'; |
142 | return ret; |
143 | } |
144 | |
145 | unsigned char *hex2bin(const char *in, int outlen) |
146 | { |
147 | unsigned char *ret = snewn(outlen, unsigned char); |
148 | int i; |
149 | |
74476385 |
150 | memset(ret, 0, outlen*sizeof(unsigned char)); |
151 | for (i = 0; i < outlen*2; i++) { |
152 | int c = in[i]; |
153 | int v; |
154 | |
155 | assert(c != 0); |
156 | if (c >= '0' && c <= '9') |
157 | v = c - '0'; |
158 | else if (c >= 'a' && c <= 'f') |
159 | v = c - 'a' + 10; |
160 | else if (c >= 'A' && c <= 'F') |
161 | v = c - 'A' + 10; |
162 | else |
163 | v = 0; |
164 | |
165 | ret[i / 2] |= v << (4 * (1 - (i % 2))); |
166 | } |
167 | return ret; |
168 | } |
169 | |
937a9eff |
170 | void game_mkhighlight(frontend *fe, float *ret, |
171 | int background, int highlight, int lowlight) |
172 | { |
173 | float max; |
174 | int i; |
175 | |
176 | frontend_default_colour(fe, &ret[background * 3]); |
177 | |
178 | /* |
179 | * Drop the background colour so that the highlight is |
180 | * noticeably brighter than it while still being under 1. |
181 | */ |
182 | max = ret[background*3]; |
183 | for (i = 1; i < 3; i++) |
184 | if (ret[background*3+i] > max) |
185 | max = ret[background*3+i]; |
186 | if (max * 1.2F > 1.0F) { |
187 | for (i = 0; i < 3; i++) |
188 | ret[background*3+i] /= (max * 1.2F); |
189 | } |
190 | |
191 | for (i = 0; i < 3; i++) { |
192 | ret[highlight * 3 + i] = ret[background * 3 + i] * 1.2F; |
193 | ret[lowlight * 3 + i] = ret[background * 3 + i] * 0.8F; |
194 | } |
195 | } |
196 | |
1ad942e7 |
197 | static void memswap(void *av, void *bv, int size) |
d74986c9 |
198 | { |
199 | char tmpbuf[512]; |
200 | char *a = av, *b = bv; |
201 | |
202 | while (size > 0) { |
203 | int thislen = min(size, sizeof(tmpbuf)); |
204 | memcpy(tmpbuf, a, thislen); |
205 | memcpy(a, b, thislen); |
206 | memcpy(b, tmpbuf, thislen); |
207 | a += thislen; |
208 | b += thislen; |
209 | size -= thislen; |
210 | } |
211 | } |
212 | |
c8305fa8 |
213 | void shuffle(void *array, int nelts, int eltsize, random_state *rs) |
214 | { |
c8305fa8 |
215 | char *carray = (char *)array; |
216 | int i; |
217 | |
218 | for (i = nelts; i-- > 1 ;) { |
219 | int j = random_upto(rs, i+1); |
d74986c9 |
220 | if (j != i) |
221 | memswap(carray + eltsize * i, carray + eltsize * j, eltsize); |
c8305fa8 |
222 | } |
223 | } |
224 | |
dafd6cf6 |
225 | void draw_rect_outline(drawing *dr, int x, int y, int w, int h, int colour) |
bf7ebf5a |
226 | { |
227 | int x0 = x, x1 = x+w-1, y0 = y, y1 = y+h-1; |
dafd6cf6 |
228 | int coords[8]; |
229 | |
230 | coords[0] = x0; |
231 | coords[1] = y0; |
232 | coords[2] = x0; |
233 | coords[3] = y1; |
234 | coords[4] = x1; |
235 | coords[5] = y1; |
236 | coords[6] = x1; |
237 | coords[7] = y0; |
238 | |
239 | draw_polygon(dr, coords, 4, -1, colour); |
bf7ebf5a |
240 | } |
241 | |
74476385 |
242 | /* vim: set shiftwidth=4 tabstop=8: */ |