1 /* $OSSEC, os_regex_internal.h, v0.3, 2005/04/05, Daniel B. Cid$ */
3 /* Copyright (C) 2009 Trend Micro Inc.
6 * This program is a free software; you can redistribute it
7 * and/or modify it under the terms of the GNU General Public
8 * License (version 2) as published by the FSF - Free Software
13 #ifndef __OS_INTERNAL_H
14 #define __OS_INTERNAL_H
17 /* Prototype fo the _OsMatch */
18 int _OS_Match(const char *pattern, const char *str, size_t str_len, size_t size) __attribute__((nonnull));
19 int _os_strncmp(const char *pattern, const char *str, size_t str_len, size_t size) __attribute__((nonnull));
20 int _os_strcmp_last(const char *pattern, const char *str, size_t str_len, size_t size) __attribute__((nonnull));
21 int _os_strcmp(const char *pattern, const char *str, size_t str_len, size_t size) __attribute__((nonnull));
22 int _os_strmatch(const char *pattern, const char *str, size_t str_len, size_t size) __attribute__((nonnull));
23 int _os_strstr(const char *pattern, const char *str, size_t str_len, size_t size) __attribute__((nonnull));
27 * Defining some caracters to be used.
29 #define BACKSLASH '\\'
32 #define BEGINREGEX '^'
42 #define BEGIN_SET 0000200
43 #define END_SET 0000400
47 typedef unsigned char uchar;
50 /* _IsD Returns 1 if it is a number */
51 #define _IsD(x) ((x >= 48) && (x <= 57))
54 /* Is it a character ?
58 #define _IsW(x) ((x >= 48 && x <= 57 )|| \
59 (x >= 65 && x <= 90 )|| \
60 (x >= 97 && x <= 122))
63 /* Is it a ' ' (blank)
67 #define _IsS(x) (x == 32)
70 /* Check for parenthesis */
71 #define prts(x) (x == '(')
75 * Returns 1 on success
77 #define isPlus(x) ((x == '+') || (x == '*'))
84 /* Is "y" a valid "x"?.
85 * Returns 1 on success
87 #define Regex(x,y) (regexmap[x][y] == TRUECHAR)
88 #define Regex2(x,y) (x == 'd' && y >= 48 && y <= 57)|| \
89 (x == 's' && y == 32)|| \
91 ((y >= 40 && y <= 46)|| \
92 (y >= 58 && y <= 63)))|| \
95 (y >= 48 && y <= 57)|| \
96 (y >= 65 && y <= 90)|| \
97 (y >= 97 && y <= 122)))|| \
99 ((x == '\\') && (y == '\\'))|| \
100 ((x == 'n') && (y == '\n'))|| \
101 (x == 'S' && y != 32)|| \
102 (x == 'D' && (y < 48 || y > 57))|| \
103 (x == 'W' && (y < 48 || y > 122 || \
104 (y > 57 && y <65)||(y > 90 && y< 97)))
107 /* Charmap for case insensitive search */
108 static const uchar charmap[] = {
109 0, 1, 2, 3, 4, 5, 6, 7,
110 8, 9, 10, 11, 12, 13, 14, 15,
111 16, 17, 18, 19, 20, 21, 22, 23,
112 24, 25, 26, 27, 28, 29, 30, 31,
113 32, 33, 34, 35, 36, 37, 38, 39,
114 40, 41, 42, 43, 44, 45, 46, 47,
115 48, 49, 50, 51, 52, 53, 54, 55,
116 56, 57, 58, 59, 60, 61, 62, 63,
117 64, 97, 98, 99, 100, 101, 102, 103,
118 104, 105, 106, 107, 108, 109, 110, 111,
119 112, 113, 114, 115, 116, 117, 118, 119,
120 120, 121, 122, 91, 92, 93, 94, 95,
121 96, 97, 98, 99, 100, 101, 102, 103,
122 104, 105, 106, 107, 108, 109, 110, 111,
123 112, 113, 114, 115, 116, 117, 118, 119,
124 120, 121, 122, 123, 124, 125, 126, 127,
125 128, 129, 130, 131, 132, 133, 134, 135,
126 136, 137, 138, 139, 140, 141, 142, 143,
127 144, 145, 146, 147, 148, 149, 150, 151,
128 152, 153, 154, 155, 156, 157, 158, 159,
129 160, 161, 162, 163, 164, 165, 166, 167,
130 168, 169, 170, 171, 172, 173, 174, 175,
131 176, 177, 178, 179, 180, 181, 182, 183,
132 184, 185, 186, 187, 188, 189, 190, 191,
133 192, 193, 194, 195, 196, 197, 198, 199,
134 200, 201, 202, 203, 204, 205, 206, 207,
135 208, 209, 210, 211, 212, 213, 214, 215,
136 216, 217, 218, 219, 220, 221, 222, 223,
137 224, 225, 226, 227, 228, 229, 230, 231,
138 232, 233, 234, 235, 236, 237, 238, 239,
139 240, 241, 242, 243, 244, 245, 246, 247,
140 248, 249, 250, 251, 252, 253, 254, 255,
163 static const uchar regexmap[][256] =
166 0, 0, 0, 0, 0, 0, 0, 0,
167 0, 0, 0, 0, 0, 0, 0, 0,
168 0, 0, 0, 0, 0, 0, 0, 0,
169 0, 0, 0, 0, 0, 0, 0, 0,
170 0, 0, 0, 0, 0, 0, 0, 0,
171 0, 0, 0, 0, 0, 0, 0, 0,
172 1, 1, 1, 1, 1, 1, 1, 1,
173 1, 1, 0, 59, 60, 61, 62, 63,
174 64, 97, 98, 99, 100, 101, 102, 103,
175 104, 105, 106, 107, 108, 109, 110, 111,
176 112, 113, 114, 115, 116, 117, 118, 119,
177 120, 121, 122, 91, 92, 93, 94, 95,
178 96, 97, 98, 99, 100, 101, 102, 103,
179 104, 105, 106, 107, 108, 109, 110, 111,
180 112, 113, 114, 115, 116, 117, 118, 119,
181 120, 121, 122, 123, 124, 125, 126, 127,
182 128, 129, 130, 131, 132, 133, 134, 135,
183 136, 137, 138, 139, 140, 141, 142, 143,
184 144, 145, 146, 147, 148, 149, 150, 151,
185 152, 153, 154, 155, 156, 157, 158, 159,
186 160, 161, 162, 163, 164, 165, 166, 167,
187 168, 169, 170, 171, 172, 173, 174, 175,
188 176, 177, 178, 179, 180, 181, 182, 183,
189 184, 185, 186, 187, 188, 189, 190, 191,
190 192, 193, 194, 195, 196, 197, 198, 199,
191 200, 201, 202, 203, 204, 205, 206, 207,
192 208, 209, 210, 211, 212, 213, 214, 215,
193 216, 217, 218, 219, 220, 221, 222, 223,
194 224, 225, 226, 227, 228, 229, 230, 231,
195 232, 233, 234, 235, 236, 237, 238, 239,
196 240, 241, 242, 243, 244, 245, 246, 247,
197 248, 249, 250, 251, 252, 253, 254, 255,
200 0, 0, 0, 0, 0, 0, 0, 0,
201 0, 0, 0, 0, 0, 0, 0, 0,
202 0, 0, 0, 0, 0, 0, 0, 0,
203 0, 0, 0, 0, 0, 0, 0, 0,
204 0, 0, 0, 0, 0, 0, 0, 0,
205 0, 0, 0, 0, 0, 0, 0, 0,
206 1, 1, 1, 1, 1, 1, 1, 1,
207 1, 1, 0, 59, 60, 61, 62, 63,
208 64, 97, 98, 99, 100, 101, 102, 103,
209 104, 105, 106, 107, 108, 109, 110, 111,
210 112, 113, 114, 115, 116, 117, 118, 119,
211 120, 121, 122, 91, 92, 93, 94, 95,
212 96, 97, 98, 99, 100, 101, 102, 103,
213 104, 105, 106, 107, 108, 109, 110, 111,
214 112, 113, 114, 115, 116, 117, 118, 119,
215 120, 121, 122, 123, 124, 125, 126, 127,
216 128, 129, 130, 131, 132, 133, 134, 135,
217 136, 137, 138, 139, 140, 141, 142, 143,
218 144, 145, 146, 147, 148, 149, 150, 151,
219 152, 153, 154, 155, 156, 157, 158, 159,
220 160, 161, 162, 163, 164, 165, 166, 167,
221 168, 169, 170, 171, 172, 173, 174, 175,
222 176, 177, 178, 179, 180, 181, 182, 183,
223 184, 185, 186, 187, 188, 189, 190, 191,
224 192, 193, 194, 195, 196, 197, 198, 199,
225 200, 201, 202, 203, 204, 205, 206, 207,
226 208, 209, 210, 211, 212, 213, 214, 215,
227 216, 217, 218, 219, 220, 221, 222, 223,
228 224, 225, 226, 227, 228, 229, 230, 231,
229 232, 233, 234, 235, 236, 237, 238, 239,
230 240, 241, 242, 243, 244, 245, 246, 247,
231 248, 249, 250, 251, 252, 253, 254, 255,
234 0, 0, 2, 3, 4, 5, 6, 7,
235 8, 9, 10, 11, 12, 13, 14, 15,
236 16, 17, 18, 19, 20, 21, 22, 23,
237 24, 25, 26, 27, 28, 29, 30, 31,
238 32, 33, 34, 35, 36, 37, 38, 39,
239 40, 41, 42, 43, 44, 1, 46, 47,
240 1, 1, 1, 1, 1, 1, 1, 1,
241 1, 1, 58, 59, 60, 61, 62, 63,
242 1, 1, 1, 1, 1, 1, 1, 1,
243 1, 1, 1, 1, 1, 1, 1, 1,
244 1, 1, 1, 1, 1, 1, 1, 1,
245 1, 1, 1, 91, 92, 93, 94, 1,
246 96, 1, 1, 1, 1, 1, 1, 1,
247 1, 1, 1, 1, 1, 1, 1, 1,
248 1, 1, 1, 1, 1, 1, 1, 1,
249 1, 1, 1, 123, 124, 125, 126, 127,
250 128, 129, 130, 131, 132, 133, 134, 135,
251 136, 137, 138, 139, 140, 141, 142, 143,
252 144, 145, 146, 147, 148, 149, 150, 151,
253 152, 153, 154, 155, 156, 157, 158, 159,
254 160, 161, 162, 163, 164, 165, 166, 167,
255 168, 169, 170, 171, 172, 173, 174, 175,
256 176, 177, 178, 179, 180, 181, 182, 183,
257 184, 185, 186, 187, 188, 189, 190, 191,
258 192, 193, 194, 195, 196, 197, 198, 199,
259 200, 201, 202, 203, 204, 205, 206, 207,
260 208, 209, 210, 211, 212, 213, 214, 215,
261 216, 217, 218, 219, 220, 221, 222, 223,
262 224, 225, 226, 227, 228, 229, 230, 231,
263 232, 233, 234, 235, 236, 237, 238, 239,
264 240, 241, 242, 243, 244, 245, 246, 247,
265 240, 241, 242, 243, 244, 245, 246, 247,
268 0, 0, 2, 3, 4, 5, 6, 7,
269 8, 9, 10, 11, 12, 13, 14, 15,
270 16, 17, 18, 19, 20, 21, 22, 23,
271 24, 25, 26, 27, 28, 29, 30, 31,
272 1, 33, 34, 35, 36, 37, 38, 39,
273 40, 41, 42, 43, 44, 45, 46, 47,
274 48, 49, 50, 51, 52, 53, 54, 55,
275 56, 57, 58, 59, 60, 61, 62, 63,
276 64, 97, 98, 99, 100, 101, 102, 103,
277 104, 105, 106, 107, 108, 109, 110, 111,
278 112, 113, 114, 115, 116, 117, 118, 119,
279 120, 121, 122, 91, 92, 93, 94, 95,
280 96, 97, 98, 99, 100, 101, 102, 103,
281 104, 105, 106, 107, 108, 109, 110, 111,
282 112, 113, 114, 115, 116, 117, 118, 119,
283 120, 121, 122, 123, 124, 125, 126, 127,
284 128, 129, 130, 131, 132, 133, 134, 135,
285 136, 137, 138, 139, 140, 141, 142, 143,
286 144, 145, 146, 147, 148, 149, 150, 151,
287 152, 153, 154, 155, 156, 157, 158, 159,
288 160, 161, 162, 163, 164, 165, 166, 167,
289 168, 169, 170, 171, 172, 173, 174, 175,
290 176, 177, 178, 179, 180, 181, 182, 183,
291 184, 185, 186, 187, 188, 189, 190, 191,
292 192, 193, 194, 195, 196, 197, 198, 199,
293 200, 201, 202, 203, 204, 205, 206, 207,
294 208, 209, 210, 211, 212, 213, 214, 215,
295 216, 217, 218, 219, 220, 221, 222, 223,
296 224, 225, 226, 227, 228, 229, 230, 231,
297 232, 233, 234, 235, 236, 237, 238, 239,
298 240, 241, 242, 243, 244, 245, 246, 247,
299 248, 249, 250, 251, 252, 253, 254, 255,
302 0, 0, 2, 3, 4, 5, 6, 7,
303 8, 9, 10, 11, 12, 13, 14, 15,
304 16, 17, 18, 19, 20, 21, 22, 23,
305 24, 25, 26, 27, 28, 29, 30, 31,
306 32, 1, 1, 1, 1, 1, 1, 1,
307 1, 1, 1, 1, 1, 1, 1, 47,
308 48, 49, 50, 51, 52, 53, 54, 55,
309 56, 57, 1, 1, 1, 1, 1, 1,
310 64, 97, 98, 99, 100, 101, 102, 103,
311 104, 105, 106, 107, 108, 109, 110, 111,
312 112, 113, 114, 115, 116, 117, 118, 119,
313 120, 121, 122, 1, 0, 1, 94, 95,
314 96, 97, 98, 99, 100, 101, 102, 103,
315 104, 105, 106, 107, 108, 109, 110, 111,
316 112, 113, 114, 115, 116, 117, 118, 119,
317 120, 121, 122, 1, 1, 1, 126, 127,
318 128, 129, 130, 131, 132, 133, 134, 135,
319 136, 137, 138, 139, 140, 141, 142, 143,
320 144, 145, 146, 147, 148, 149, 150, 151,
321 152, 153, 154, 155, 156, 157, 158, 159,
322 160, 161, 162, 163, 164, 165, 166, 167,
323 168, 169, 170, 171, 172, 173, 174, 175,
324 176, 177, 178, 179, 180, 181, 182, 183,
325 184, 185, 186, 187, 188, 189, 190, 191,
326 192, 193, 194, 195, 196, 197, 198, 199,
327 200, 201, 202, 203, 204, 205, 206, 207,
328 208, 209, 210, 211, 212, 213, 214, 215,
329 216, 217, 218, 219, 220, 221, 222, 223,
330 224, 225, 226, 227, 228, 229, 230, 231,
331 232, 233, 234, 235, 236, 237, 238, 239,
332 240, 241, 242, 243, 244, 245, 246, 247,
333 248, 249, 250, 251, 252, 253, 254, 255,
336 0, 0, 0, 0, 0, 0, 0, 0,
337 0, 0, 0, 0, 0, 0, 0, 0,
338 0, 0, 0, 0, 0, 0, 0, 0,
339 0, 0, 0, 0, 0, 0, 0, 0,
340 0, 0, 0, 0, 0, 0, 0, 0,
341 1, 0, 0, 0, 0, 0, 0, 0,
342 0, 0, 0, 0, 0, 0, 0, 0,
343 0, 0, 0, 0, 0, 0, 0, 0,
344 0, 0, 0, 0, 0, 0, 0, 0,
345 0, 0, 0, 0, 0, 0, 0, 0,
346 0, 0, 0, 0, 0, 0, 0, 0,
347 0, 0, 0, 0, 0, 0, 0, 0,
348 0, 0, 0, 0, 0, 0, 0, 0,
349 0, 0, 0, 0, 0, 0, 0, 0,
350 0, 0, 0, 0, 0, 0, 0, 0,
351 0, 0, 0, 0, 0, 0, 0, 0,
352 0, 0, 0, 0, 0, 0, 0, 0,
353 0, 0, 0, 0, 0, 0, 0, 0,
354 0, 0, 0, 0, 0, 0, 0, 0,
355 0, 0, 0, 0, 0, 0, 0, 0,
356 0, 0, 0, 0, 0, 0, 0, 0,
357 0, 0, 0, 0, 0, 0, 0, 0,
358 0, 0, 0, 0, 0, 0, 0, 0,
359 0, 0, 0, 0, 0, 0, 0, 0,
360 0, 0, 0, 0, 0, 0, 0, 0,
361 0, 0, 0, 0, 0, 0, 0, 0,
362 0, 0, 0, 0, 0, 0, 0, 0,
363 0, 0, 0, 0, 0, 0, 0, 0,
364 0, 0, 0, 0, 0, 0, 0, 0,
365 0, 0, 0, 0, 0, 0, 0, 0,
366 0, 0, 0, 0, 0, 0, 0, 0,
367 0, 0, 0, 0, 0, 0, 0, 0,
370 0, 0, 0, 0, 0, 0, 0, 0,
371 0, 0, 0, 0, 0, 0, 0, 0,
372 0, 0, 0, 0, 0, 0, 0, 0,
373 0, 0, 0, 0, 0, 0, 0, 0,
374 0, 0, 0, 0, 0, 0, 0, 0,
375 0, 1, 0, 0, 0, 0, 0, 0,
376 0, 0, 0, 0, 0, 0, 0, 0,
377 0, 0, 0, 0, 0, 0, 0, 0,
378 0, 0, 0, 0, 0, 0, 0, 0,
379 0, 0, 0, 0, 0, 0, 0, 0,
380 0, 0, 0, 0, 0, 0, 0, 0,
381 0, 0, 0, 0, 0, 0, 0, 0,
382 0, 0, 0, 0, 0, 0, 0, 0,
383 0, 0, 0, 0, 0, 0, 0, 0,
384 0, 0, 0, 0, 0, 0, 0, 0,
385 0, 0, 0, 0, 0, 0, 0, 0,
386 0, 0, 0, 0, 0, 0, 0, 0,
387 0, 0, 0, 0, 0, 0, 0, 0,
388 0, 0, 0, 0, 0, 0, 0, 0,
389 0, 0, 0, 0, 0, 0, 0, 0,
390 0, 0, 0, 0, 0, 0, 0, 0,
391 0, 0, 0, 0, 0, 0, 0, 0,
392 0, 0, 0, 0, 0, 0, 0, 0,
393 0, 0, 0, 0, 0, 0, 0, 0,
394 0, 0, 0, 0, 0, 0, 0, 0,
395 0, 0, 0, 0, 0, 0, 0, 0,
396 0, 0, 0, 0, 0, 0, 0, 0,
397 0, 0, 0, 0, 0, 0, 0, 0,
398 0, 0, 0, 0, 0, 0, 0, 0,
399 0, 0, 0, 0, 0, 0, 0, 0,
400 0, 0, 0, 0, 0, 0, 0, 0,
401 0, 0, 0, 0, 0, 0, 0, 0,
404 0, 0, 0, 0, 0, 0, 0, 0,
405 0, 0, 0, 0, 0, 0, 0, 0,
406 0, 0, 0, 0, 0, 0, 0, 0,
407 0, 0, 0, 0, 0, 0, 0, 0,
408 0, 0, 0, 0, 0, 0, 0, 0,
409 0, 0, 0, 0, 0, 0, 0, 0,
410 0, 0, 0, 0, 0, 0, 0, 0,
411 0, 0, 0, 0, 0, 0, 0, 0,
412 0, 0, 0, 0, 0, 0, 0, 0,
413 0, 0, 0, 0, 0, 0, 0, 0,
414 0, 0, 0, 0, 0, 0, 0, 0,
415 0, 0, 0, 0, 1, 0, 0, 0,
416 0, 0, 0, 0, 0, 0, 0, 0,
417 0, 0, 0, 0, 0, 0, 0, 0,
418 0, 0, 0, 0, 0, 0, 0, 0,
419 0, 0, 0, 0, 0, 0, 0, 0,
420 0, 0, 0, 0, 0, 0, 0, 0,
421 0, 0, 0, 0, 0, 0, 0, 0,
422 0, 0, 0, 0, 0, 0, 0, 0,
423 0, 0, 0, 0, 0, 0, 0, 0,
424 0, 0, 0, 0, 0, 0, 0, 0,
425 0, 0, 0, 0, 0, 0, 0, 0,
426 0, 0, 0, 0, 0, 0, 0, 0,
427 0, 0, 0, 0, 0, 0, 0, 0,
428 0, 0, 0, 0, 0, 0, 0, 0,
429 0, 0, 0, 0, 0, 0, 0, 0,
430 0, 0, 0, 0, 0, 0, 0, 0,
431 0, 0, 0, 0, 0, 0, 0, 0,
432 0, 0, 0, 0, 0, 0, 0, 0,
433 0, 0, 0, 0, 0, 0, 0, 0,
434 0, 0, 0, 0, 0, 0, 0, 0,
435 0, 0, 0, 0, 0, 0, 0, 0,
438 1, 1, 1, 1, 1, 1, 1, 1,
439 1, 1, 1, 1, 1, 1, 1, 1,
440 1, 1, 1, 1, 1, 1, 1, 1,
441 1, 1, 1, 1, 1, 1, 1, 1,
442 1, 1, 1, 1, 1, 1, 1, 1,
443 1, 1, 1, 1, 1, 1, 1, 1,
444 0, 0, 0, 0, 0, 0, 0, 0,
445 0, 0, 1, 1, 1, 1, 1, 1,
446 1, 1, 1, 1, 1, 1, 1, 1,
447 1, 1, 1, 1, 1, 1, 1, 1,
448 1, 1, 1, 1, 1, 1, 1, 1,
449 1, 1, 1, 1, 1, 1, 1, 1,
450 1, 1, 1, 1, 1, 1, 1, 1,
451 1, 1, 1, 1, 1, 1, 1, 1,
452 1, 1, 1, 1, 1, 1, 1, 1,
453 1, 1, 1, 1, 1, 1, 1, 1,
454 1, 1, 1, 1, 1, 1, 1, 1,
455 1, 1, 1, 1, 1, 1, 1, 1,
456 1, 1, 1, 1, 1, 1, 1, 1,
457 1, 1, 1, 1, 1, 1, 1, 1,
458 1, 1, 1, 1, 1, 1, 1, 1,
459 1, 1, 1, 1, 1, 1, 1, 1,
460 1, 1, 1, 1, 1, 1, 1, 1,
461 1, 1, 1, 1, 1, 1, 1, 1,
462 1, 1, 1, 1, 1, 1, 1, 1,
463 1, 1, 1, 1, 1, 1, 1, 1,
464 1, 1, 1, 1, 1, 1, 1, 1,
465 1, 1, 1, 1, 1, 1, 1, 1,
466 1, 1, 1, 1, 1, 1, 1, 1,
467 1, 1, 1, 1, 1, 1, 1, 1,
468 1, 1, 1, 1, 1, 1, 1, 1,
469 1, 1, 1, 1, 1, 1, 1, 1,
472 1, 1, 1, 1, 1, 1, 1, 1,
473 1, 1, 1, 1, 1, 1, 1, 1,
474 1, 1, 1, 1, 1, 1, 1, 1,
475 1, 1, 1, 1, 1, 1, 1, 1,
476 1, 1, 1, 1, 1, 1, 1, 1,
477 1, 1, 1, 1, 1, 1, 1, 1,
478 0, 0, 0, 0, 0, 0, 0, 0,
479 0, 0, 1, 1, 1, 1, 1, 1,
480 1, 0, 0, 0, 0, 0, 0, 0,
481 0, 0, 0, 0, 0, 0, 0, 0,
482 0, 0, 0, 0, 0, 0, 0, 0,
483 0, 0, 0, 1, 1, 1, 1, 0,
484 1, 0, 0, 0, 0, 0, 0, 0,
485 0, 0, 0, 0, 0, 0, 0, 0,
486 0, 0, 0, 0, 0, 0, 0, 0,
487 0, 0, 0, 1, 1, 1, 1, 0,
488 1, 1, 1, 1, 1, 1, 1, 1,
489 1, 1, 1, 1, 1, 1, 1, 1,
490 1, 1, 1, 1, 1, 1, 1, 1,
491 1, 1, 1, 1, 1, 1, 1, 1,
492 1, 1, 1, 1, 1, 1, 1, 1,
493 1, 1, 1, 1, 1, 1, 1, 1,
494 1, 1, 1, 1, 1, 1, 1, 1,
495 1, 1, 1, 1, 1, 1, 1, 1,
496 1, 1, 1, 1, 1, 1, 1, 1,
497 1, 1, 1, 1, 1, 1, 1, 1,
498 1, 1, 1, 1, 1, 1, 1, 1,
499 1, 1, 1, 1, 1, 1, 1, 1,
500 1, 1, 1, 1, 1, 1, 1, 1,
501 1, 1, 1, 1, 1, 1, 1, 1,
502 1, 1, 1, 1, 1, 1, 1, 1,
503 1, 1, 1, 1, 1, 1, 1, 1,
506 1, 1, 1, 1, 1, 1, 1, 1,
507 1, 1, 1, 1, 1, 1, 1, 1,
508 1, 1, 1, 1, 1, 1, 1, 1,
509 1, 1, 1, 1, 1, 1, 1, 1,
510 0, 1, 1, 1, 1, 1, 1, 1,
511 1, 1, 1, 1, 1, 1, 1, 1,
512 1, 1, 1, 1, 1, 1, 1, 1,
513 1, 1, 1, 1, 1, 1, 1, 1,
514 1, 1, 1, 1, 1, 1, 1, 1,
515 1, 1, 1, 1, 1, 1, 1, 1,
516 1, 1, 1, 1, 1, 1, 1, 1,
517 1, 1, 1, 1, 1, 1, 1, 1,
518 1, 1, 1, 1, 1, 1, 1, 1,
519 1, 1, 1, 1, 1, 1, 1, 1,
520 1, 1, 1, 1, 1, 1, 1, 1,
521 1, 1, 1, 1, 1, 1, 1, 1,
522 1, 1, 1, 1, 1, 1, 1, 1,
523 1, 1, 1, 1, 1, 1, 1, 1,
524 1, 1, 1, 1, 1, 1, 1, 1,
525 1, 1, 1, 1, 1, 1, 1, 1,
526 1, 1, 1, 1, 1, 1, 1, 1,
527 1, 1, 1, 1, 1, 1, 1, 1,
528 1, 1, 1, 1, 1, 1, 1, 1,
529 1, 1, 1, 1, 1, 1, 1, 1,
530 1, 1, 1, 1, 1, 1, 1, 1,
531 1, 1, 1, 1, 1, 1, 1, 1,
532 1, 1, 1, 1, 1, 1, 1, 1,
533 1, 1, 1, 1, 1, 1, 1, 1,
534 1, 1, 1, 1, 1, 1, 1, 1,
535 1, 1, 1, 1, 1, 1, 1, 1,
536 1, 1, 1, 1, 1, 1, 1, 1,
537 1, 1, 1, 1, 1, 1, 1, 1,
540 1, 1, 1, 1, 1, 1, 1, 1,
541 1, 1, 1, 1, 1, 1, 1, 1,
542 1, 1, 1, 1, 1, 1, 1, 1,
543 1, 1, 1, 1, 1, 1, 1, 1,
544 1, 1, 1, 1, 1, 1, 1, 1,
545 1, 1, 1, 1, 1, 1, 1, 1,
546 1, 1, 1, 1, 1, 1, 1, 1,
547 1, 1, 1, 1, 1, 1, 1, 1,
548 1, 1, 1, 1, 1, 1, 1, 1,
549 1, 1, 1, 1, 1, 1, 1, 1,
550 1, 1, 1, 1, 1, 1, 1, 1,
551 1, 1, 1, 1, 1, 1, 1, 1,
552 1, 1, 1, 1, 1, 1, 1, 1,
553 1, 1, 1, 1, 1, 1, 1, 1,
554 1, 1, 1, 1, 1, 1, 1, 1,
555 1, 1, 1, 1, 1, 1, 1, 1,
556 1, 1, 1, 1, 1, 1, 1, 1,
557 1, 1, 1, 1, 1, 1, 1, 1,
558 1, 1, 1, 1, 1, 1, 1, 1,
559 1, 1, 1, 1, 1, 1, 1, 1,
560 1, 1, 1, 1, 1, 1, 1, 1,
561 1, 1, 1, 1, 1, 1, 1, 1,
562 1, 1, 1, 1, 1, 1, 1, 1,
563 1, 1, 1, 1, 1, 1, 1, 1,
564 1, 1, 1, 1, 1, 1, 1, 1,
565 1, 1, 1, 1, 1, 1, 1, 1,
566 1, 1, 1, 1, 1, 1, 1, 1,
567 1, 1, 1, 1, 1, 1, 1, 1,
568 1, 1, 1, 1, 1, 1, 1, 1,
569 1, 1, 1, 1, 1, 1, 1, 1,
570 1, 1, 1, 1, 1, 1, 1, 1,
571 1, 1, 1, 1, 1, 1, 1, 1,
574 0, 0, 2, 3, 4, 5, 6, 7,
575 8, 1, 10, 11, 12, 13, 14, 15,
576 16, 17, 18, 19, 20, 21, 22, 23,
577 24, 25, 26, 27, 28, 29, 30, 31,
578 32, 33, 34, 35, 36, 37, 38, 39,
579 40, 41, 42, 43, 44, 45, 46, 47,
580 48, 49, 50, 51, 52, 53, 54, 55,
581 56, 57, 58, 59, 60, 61, 62, 63,
582 64, 97, 98, 99, 100, 101, 102, 103,
583 104, 105, 106, 107, 108, 109, 110, 111,
584 112, 113, 114, 115, 116, 117, 118, 119,
585 120, 121, 122, 91, 92, 93, 94, 95,
586 96, 97, 98, 99, 100, 101, 102, 103,
587 104, 105, 106, 107, 108, 109, 110, 111,
588 112, 113, 114, 115, 116, 117, 118, 119,
589 120, 121, 122, 123, 124, 125, 126, 127,
590 128, 129, 130, 131, 132, 133, 134, 135,
591 136, 137, 138, 139, 140, 141, 142, 143,
592 144, 145, 146, 147, 148, 149, 150, 151,
593 152, 153, 154, 155, 156, 157, 158, 159,
594 160, 161, 162, 163, 164, 165, 166, 167,
595 168, 169, 170, 171, 172, 173, 174, 175,
596 176, 177, 178, 179, 180, 181, 182, 183,
597 184, 185, 186, 187, 188, 189, 190, 191,
598 192, 193, 194, 195, 196, 197, 198, 199,
599 200, 201, 202, 203, 204, 205, 206, 207,
600 208, 209, 210, 211, 212, 213, 214, 215,
601 216, 217, 218, 219, 220, 221, 222, 223,
602 224, 225, 226, 227, 228, 229, 230, 231,
603 232, 233, 234, 235, 236, 237, 238, 239,
604 240, 241, 242, 243, 244, 245, 246, 247,
605 248, 249, 250, 251, 252, 253, 254, 255,
608 0, 0, 2, 3, 4, 5, 6, 7,
609 8, 10, 10, 11, 12, 13, 14, 15,
610 16, 17, 18, 19, 20, 21, 22, 23,
611 24, 25, 26, 27, 28, 29, 30, 31,
612 32, 33, 34, 35, 1, 37, 38, 39,
613 40, 41, 42, 43, 44, 45, 46, 47,
614 48, 49, 50, 51, 52, 53, 54, 55,
615 56, 57, 58, 59, 60, 61, 62, 63,
616 64, 97, 98, 99, 100, 101, 102, 103,
617 104, 105, 106, 107, 108, 109, 110, 111,
618 112, 113, 114, 115, 116, 117, 118, 119,
619 120, 121, 122, 91, 92, 93, 94, 95,
620 96, 97, 98, 99, 100, 101, 102, 103,
621 104, 105, 106, 107, 108, 109, 110, 111,
622 112, 113, 114, 115, 116, 117, 118, 119,
623 120, 121, 122, 123, 124, 125, 126, 127,
624 128, 129, 130, 131, 132, 133, 134, 135,
625 136, 137, 138, 139, 140, 141, 142, 143,
626 144, 145, 146, 147, 148, 149, 150, 151,
627 152, 153, 154, 155, 156, 157, 158, 159,
628 160, 161, 162, 163, 164, 165, 166, 167,
629 168, 169, 170, 171, 172, 173, 174, 175,
630 176, 177, 178, 179, 180, 181, 182, 183,
631 184, 185, 186, 187, 188, 189, 190, 191,
632 192, 193, 194, 195, 196, 197, 198, 199,
633 200, 201, 202, 203, 204, 205, 206, 207,
634 208, 209, 210, 211, 212, 213, 214, 215,
635 216, 217, 218, 219, 220, 221, 222, 223,
636 224, 225, 226, 227, 228, 229, 230, 231,
637 232, 233, 234, 235, 236, 237, 238, 239,
638 240, 241, 242, 243, 244, 245, 246, 247,
639 248, 249, 250, 251, 252, 253, 254, 255,
642 0, 0, 2, 3, 4, 5, 6, 7,
643 8, 10, 10, 11, 12, 13, 14, 15,
644 16, 17, 18, 19, 20, 21, 22, 23,
645 24, 25, 26, 27, 28, 29, 30, 31,
646 32, 33, 34, 35, 36, 37, 38, 39,
647 40, 41, 42, 43, 44, 45, 46, 47,
648 48, 49, 50, 51, 52, 53, 54, 55,
649 56, 57, 58, 59, 60, 61, 62, 63,
650 64, 97, 98, 99, 100, 101, 102, 103,
651 104, 105, 106, 107, 108, 109, 110, 111,
652 112, 113, 114, 115, 116, 117, 118, 119,
653 120, 121, 122, 91, 92, 93, 94, 95,
654 96, 97, 98, 99, 100, 101, 102, 103,
655 104, 105, 106, 107, 108, 109, 110, 111,
656 112, 113, 114, 115, 116, 117, 118, 119,
657 120, 121, 122, 123, 1, 125, 126, 127,
658 128, 129, 130, 131, 132, 133, 134, 135,
659 136, 137, 138, 139, 140, 141, 142, 143,
660 144, 145, 146, 147, 148, 149, 150, 151,
661 152, 153, 154, 155, 156, 157, 158, 159,
662 160, 161, 162, 163, 164, 165, 166, 167,
663 168, 169, 170, 171, 172, 173, 174, 175,
664 176, 177, 178, 179, 180, 181, 182, 183,
665 184, 185, 186, 187, 188, 189, 190, 191,
666 192, 193, 194, 195, 196, 197, 198, 199,
667 200, 201, 202, 203, 204, 205, 206, 207,
668 208, 209, 210, 211, 212, 213, 214, 215,
669 216, 217, 218, 219, 220, 221, 222, 223,
670 224, 225, 226, 227, 228, 229, 230, 231,
671 232, 233, 234, 235, 236, 237, 238, 239,
672 240, 241, 242, 243, 244, 245, 246, 247,
673 248, 249, 250, 251, 252, 253, 254, 255,
678 0, 0, 2, 3, 4, 5, 6, 7,
679 8, 10, 10, 11, 12, 13, 14, 15,
680 16, 17, 18, 19, 20, 21, 22, 23,
681 24, 25, 26, 27, 28, 29, 30, 31,
682 32, 33, 34, 35, 36, 37, 38, 39,
683 40, 41, 42, 43, 44, 45, 46, 47,
684 48, 49, 50, 51, 52, 53, 54, 55,
685 56, 57, 58, 59, 1, 61, 62, 63,
686 64, 97, 98, 99, 100, 101, 102, 103,
687 104, 105, 106, 107, 108, 109, 110, 111,
688 112, 113, 114, 115, 116, 117, 118, 119,
689 120, 121, 122, 91, 92, 93, 94, 95,
690 96, 97, 98, 99, 100, 101, 102, 103,
691 104, 105, 106, 107, 108, 109, 110, 111,
692 112, 113, 114, 115, 116, 117, 118, 119,
693 120, 121, 122, 123, 124, 125, 126, 127,
694 128, 129, 130, 131, 132, 133, 134, 135,
695 136, 137, 138, 139, 140, 141, 142, 143,
696 144, 145, 146, 147, 148, 149, 150, 151,
697 152, 153, 154, 155, 156, 157, 158, 159,
698 160, 161, 162, 163, 164, 165, 166, 167,
699 168, 169, 170, 171, 172, 173, 174, 175,
700 176, 177, 178, 179, 180, 181, 182, 183,
701 184, 185, 186, 187, 188, 189, 190, 191,
702 192, 193, 194, 195, 196, 197, 198, 199,
703 200, 201, 202, 203, 204, 205, 206, 207,
704 208, 209, 210, 211, 212, 213, 214, 215,
705 216, 217, 218, 219, 220, 221, 222, 223,
706 224, 225, 226, 227, 228, 229, 230, 231,
707 232, 233, 234, 235, 236, 237, 238, 239,
708 240, 241, 242, 243, 244, 245, 246, 247,
709 248, 249, 250, 251, 252, 253, 254, 255,