Commit | Line | Data |
---|---|---|
cf396142 AW |
1 | /* Copyright (C) 1995,1996,1997,1998,2000,2001,2002,2003,2004, 2005, 2006, 2009 Free Software Foundation, Inc. |
2 | * | |
3 | * This library is free software; you can redistribute it and/or | |
4 | * modify it under the terms of the GNU Lesser General Public License | |
5 | * as published by the Free Software Foundation; either version 3 of | |
6 | * the License, or (at your option) any later version. | |
7 | * | |
8 | * This library is distributed in the hope that it will be useful, but | |
9 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
11 | * Lesser General Public License for more details. | |
12 | * | |
13 | * You should have received a copy of the GNU Lesser General Public | |
14 | * License along with this library; if not, write to the Free Software | |
15 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA | |
16 | * 02110-1301 USA | |
17 | */ | |
18 | ||
19 | ||
20 | \f | |
21 | ||
22 | #ifdef HAVE_CONFIG_H | |
23 | # include <config.h> | |
24 | #endif | |
25 | ||
26 | #include <string.h> | |
27 | ||
28 | #include "libguile/_scm.h" | |
29 | #include "libguile/__scm.h" | |
30 | #include "libguile/smob.h" | |
31 | #include "libguile/strings.h" | |
32 | #include "libguile/array-handle.h" | |
33 | #include "libguile/bitvectors.h" | |
2fa901a5 | 34 | #include "libguile/arrays.h" |
f332e957 | 35 | #include "libguile/generalized-vectors.h" |
943a0a87 | 36 | #include "libguile/srfi-4.h" |
cf396142 AW |
37 | |
38 | /* Bit vectors. Would be nice if they were implemented on top of bytevectors, | |
39 | * but alack, all we have is this crufty C. | |
40 | */ | |
41 | ||
42 | static scm_t_bits scm_tc16_bitvector; | |
43 | ||
44 | #define IS_BITVECTOR(obj) SCM_SMOB_PREDICATE(scm_tc16_bitvector,(obj)) | |
45 | #define BITVECTOR_BITS(obj) ((scm_t_uint32 *)SCM_SMOB_DATA(obj)) | |
46 | #define BITVECTOR_LENGTH(obj) ((size_t)SCM_SMOB_DATA_2(obj)) | |
47 | ||
48 | static size_t | |
49 | bitvector_free (SCM vec) | |
50 | { | |
51 | scm_gc_free (BITVECTOR_BITS (vec), | |
52 | sizeof (scm_t_uint32) * ((BITVECTOR_LENGTH (vec)+31)/32), | |
53 | "bitvector"); | |
54 | return 0; | |
55 | } | |
56 | ||
57 | static int | |
58 | bitvector_print (SCM vec, SCM port, scm_print_state *pstate) | |
59 | { | |
60 | size_t bit_len = BITVECTOR_LENGTH (vec); | |
61 | size_t word_len = (bit_len+31)/32; | |
62 | scm_t_uint32 *bits = BITVECTOR_BITS (vec); | |
63 | size_t i, j; | |
64 | ||
65 | scm_puts ("#*", port); | |
66 | for (i = 0; i < word_len; i++, bit_len -= 32) | |
67 | { | |
68 | scm_t_uint32 mask = 1; | |
69 | for (j = 0; j < 32 && j < bit_len; j++, mask <<= 1) | |
70 | scm_putc ((bits[i] & mask)? '1' : '0', port); | |
71 | } | |
72 | ||
73 | return 1; | |
74 | } | |
75 | ||
76 | static SCM | |
77 | bitvector_equalp (SCM vec1, SCM vec2) | |
78 | { | |
79 | size_t bit_len = BITVECTOR_LENGTH (vec1); | |
80 | size_t word_len = (bit_len + 31) / 32; | |
81 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - bit_len); | |
82 | scm_t_uint32 *bits1 = BITVECTOR_BITS (vec1); | |
83 | scm_t_uint32 *bits2 = BITVECTOR_BITS (vec2); | |
84 | ||
85 | /* compare lengths */ | |
86 | if (BITVECTOR_LENGTH (vec2) != bit_len) | |
87 | return SCM_BOOL_F; | |
88 | /* avoid underflow in word_len-1 below. */ | |
89 | if (bit_len == 0) | |
90 | return SCM_BOOL_T; | |
91 | /* compare full words */ | |
92 | if (memcmp (bits1, bits2, sizeof (scm_t_uint32) * (word_len-1))) | |
93 | return SCM_BOOL_F; | |
94 | /* compare partial last words */ | |
95 | if ((bits1[word_len-1] & last_mask) != (bits2[word_len-1] & last_mask)) | |
96 | return SCM_BOOL_F; | |
97 | return SCM_BOOL_T; | |
98 | } | |
99 | ||
100 | int | |
101 | scm_is_bitvector (SCM vec) | |
102 | { | |
103 | return IS_BITVECTOR (vec); | |
104 | } | |
105 | ||
106 | SCM_DEFINE (scm_bitvector_p, "bitvector?", 1, 0, 0, | |
107 | (SCM obj), | |
108 | "Return @code{#t} when @var{obj} is a bitvector, else\n" | |
109 | "return @code{#f}.") | |
110 | #define FUNC_NAME s_scm_bitvector_p | |
111 | { | |
112 | return scm_from_bool (scm_is_bitvector (obj)); | |
113 | } | |
114 | #undef FUNC_NAME | |
115 | ||
116 | SCM | |
117 | scm_c_make_bitvector (size_t len, SCM fill) | |
118 | { | |
119 | size_t word_len = (len + 31) / 32; | |
120 | scm_t_uint32 *bits; | |
121 | SCM res; | |
122 | ||
123 | bits = scm_gc_malloc (sizeof (scm_t_uint32) * word_len, | |
124 | "bitvector"); | |
125 | SCM_NEWSMOB2 (res, scm_tc16_bitvector, bits, len); | |
126 | ||
127 | if (!SCM_UNBNDP (fill)) | |
128 | scm_bitvector_fill_x (res, fill); | |
129 | ||
130 | return res; | |
131 | } | |
132 | ||
133 | SCM_DEFINE (scm_make_bitvector, "make-bitvector", 1, 1, 0, | |
134 | (SCM len, SCM fill), | |
135 | "Create a new bitvector of length @var{len} and\n" | |
136 | "optionally initialize all elements to @var{fill}.") | |
137 | #define FUNC_NAME s_scm_make_bitvector | |
138 | { | |
139 | return scm_c_make_bitvector (scm_to_size_t (len), fill); | |
140 | } | |
141 | #undef FUNC_NAME | |
142 | ||
143 | SCM_DEFINE (scm_bitvector, "bitvector", 0, 0, 1, | |
144 | (SCM bits), | |
145 | "Create a new bitvector with the arguments as elements.") | |
146 | #define FUNC_NAME s_scm_bitvector | |
147 | { | |
148 | return scm_list_to_bitvector (bits); | |
149 | } | |
150 | #undef FUNC_NAME | |
151 | ||
152 | size_t | |
153 | scm_c_bitvector_length (SCM vec) | |
154 | { | |
155 | scm_assert_smob_type (scm_tc16_bitvector, vec); | |
156 | return BITVECTOR_LENGTH (vec); | |
157 | } | |
158 | ||
159 | SCM_DEFINE (scm_bitvector_length, "bitvector-length", 1, 0, 0, | |
160 | (SCM vec), | |
161 | "Return the length of the bitvector @var{vec}.") | |
162 | #define FUNC_NAME s_scm_bitvector_length | |
163 | { | |
164 | return scm_from_size_t (scm_c_bitvector_length (vec)); | |
165 | } | |
166 | #undef FUNC_NAME | |
167 | ||
168 | const scm_t_uint32 * | |
169 | scm_array_handle_bit_elements (scm_t_array_handle *h) | |
170 | { | |
171 | return scm_array_handle_bit_writable_elements (h); | |
172 | } | |
173 | ||
174 | scm_t_uint32 * | |
175 | scm_array_handle_bit_writable_elements (scm_t_array_handle *h) | |
176 | { | |
177 | SCM vec = h->array; | |
178 | if (SCM_I_ARRAYP (vec)) | |
179 | vec = SCM_I_ARRAY_V (vec); | |
180 | if (IS_BITVECTOR (vec)) | |
181 | return BITVECTOR_BITS (vec) + h->base/32; | |
182 | scm_wrong_type_arg_msg (NULL, 0, h->array, "bit array"); | |
183 | } | |
184 | ||
185 | size_t | |
186 | scm_array_handle_bit_elements_offset (scm_t_array_handle *h) | |
187 | { | |
188 | return h->base % 32; | |
189 | } | |
190 | ||
191 | const scm_t_uint32 * | |
192 | scm_bitvector_elements (SCM vec, | |
193 | scm_t_array_handle *h, | |
194 | size_t *offp, | |
195 | size_t *lenp, | |
196 | ssize_t *incp) | |
197 | { | |
198 | return scm_bitvector_writable_elements (vec, h, offp, lenp, incp); | |
199 | } | |
200 | ||
201 | ||
202 | scm_t_uint32 * | |
203 | scm_bitvector_writable_elements (SCM vec, | |
204 | scm_t_array_handle *h, | |
205 | size_t *offp, | |
206 | size_t *lenp, | |
207 | ssize_t *incp) | |
208 | { | |
209 | scm_generalized_vector_get_handle (vec, h); | |
210 | if (offp) | |
211 | { | |
212 | scm_t_array_dim *dim = scm_array_handle_dims (h); | |
213 | *offp = scm_array_handle_bit_elements_offset (h); | |
214 | *lenp = dim->ubnd - dim->lbnd + 1; | |
215 | *incp = dim->inc; | |
216 | } | |
217 | return scm_array_handle_bit_writable_elements (h); | |
218 | } | |
219 | ||
220 | SCM | |
221 | scm_c_bitvector_ref (SCM vec, size_t idx) | |
222 | { | |
223 | scm_t_array_handle handle; | |
224 | const scm_t_uint32 *bits; | |
225 | ||
226 | if (IS_BITVECTOR (vec)) | |
227 | { | |
228 | if (idx >= BITVECTOR_LENGTH (vec)) | |
229 | scm_out_of_range (NULL, scm_from_size_t (idx)); | |
230 | bits = BITVECTOR_BITS(vec); | |
231 | return scm_from_bool (bits[idx/32] & (1L << (idx%32))); | |
232 | } | |
233 | else | |
234 | { | |
235 | SCM res; | |
236 | size_t len, off; | |
237 | ssize_t inc; | |
238 | ||
239 | bits = scm_bitvector_elements (vec, &handle, &off, &len, &inc); | |
240 | if (idx >= len) | |
241 | scm_out_of_range (NULL, scm_from_size_t (idx)); | |
242 | idx = idx*inc + off; | |
243 | res = scm_from_bool (bits[idx/32] & (1L << (idx%32))); | |
244 | scm_array_handle_release (&handle); | |
245 | return res; | |
246 | } | |
247 | } | |
248 | ||
249 | SCM_DEFINE (scm_bitvector_ref, "bitvector-ref", 2, 0, 0, | |
250 | (SCM vec, SCM idx), | |
251 | "Return the element at index @var{idx} of the bitvector\n" | |
252 | "@var{vec}.") | |
253 | #define FUNC_NAME s_scm_bitvector_ref | |
254 | { | |
255 | return scm_c_bitvector_ref (vec, scm_to_size_t (idx)); | |
256 | } | |
257 | #undef FUNC_NAME | |
258 | ||
259 | void | |
260 | scm_c_bitvector_set_x (SCM vec, size_t idx, SCM val) | |
261 | { | |
262 | scm_t_array_handle handle; | |
263 | scm_t_uint32 *bits, mask; | |
264 | ||
265 | if (IS_BITVECTOR (vec)) | |
266 | { | |
267 | if (idx >= BITVECTOR_LENGTH (vec)) | |
268 | scm_out_of_range (NULL, scm_from_size_t (idx)); | |
269 | bits = BITVECTOR_BITS(vec); | |
270 | } | |
271 | else | |
272 | { | |
273 | size_t len, off; | |
274 | ssize_t inc; | |
275 | ||
276 | bits = scm_bitvector_writable_elements (vec, &handle, &off, &len, &inc); | |
277 | if (idx >= len) | |
278 | scm_out_of_range (NULL, scm_from_size_t (idx)); | |
279 | idx = idx*inc + off; | |
280 | } | |
281 | ||
282 | mask = 1L << (idx%32); | |
283 | if (scm_is_true (val)) | |
284 | bits[idx/32] |= mask; | |
285 | else | |
286 | bits[idx/32] &= ~mask; | |
287 | ||
288 | if (!IS_BITVECTOR (vec)) | |
289 | scm_array_handle_release (&handle); | |
290 | } | |
291 | ||
292 | SCM_DEFINE (scm_bitvector_set_x, "bitvector-set!", 3, 0, 0, | |
293 | (SCM vec, SCM idx, SCM val), | |
294 | "Set the element at index @var{idx} of the bitvector\n" | |
295 | "@var{vec} when @var{val} is true, else clear it.") | |
296 | #define FUNC_NAME s_scm_bitvector_set_x | |
297 | { | |
298 | scm_c_bitvector_set_x (vec, scm_to_size_t (idx), val); | |
299 | return SCM_UNSPECIFIED; | |
300 | } | |
301 | #undef FUNC_NAME | |
302 | ||
303 | SCM_DEFINE (scm_bitvector_fill_x, "bitvector-fill!", 2, 0, 0, | |
304 | (SCM vec, SCM val), | |
305 | "Set all elements of the bitvector\n" | |
306 | "@var{vec} when @var{val} is true, else clear them.") | |
307 | #define FUNC_NAME s_scm_bitvector_fill_x | |
308 | { | |
309 | scm_t_array_handle handle; | |
310 | size_t off, len; | |
311 | ssize_t inc; | |
312 | scm_t_uint32 *bits; | |
313 | ||
314 | bits = scm_bitvector_writable_elements (vec, &handle, | |
315 | &off, &len, &inc); | |
316 | ||
317 | if (off == 0 && inc == 1 && len > 0) | |
318 | { | |
319 | /* the usual case | |
320 | */ | |
321 | size_t word_len = (len + 31) / 32; | |
322 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - len); | |
323 | ||
324 | if (scm_is_true (val)) | |
325 | { | |
326 | memset (bits, 0xFF, sizeof(scm_t_uint32)*(word_len-1)); | |
327 | bits[word_len-1] |= last_mask; | |
328 | } | |
329 | else | |
330 | { | |
331 | memset (bits, 0x00, sizeof(scm_t_uint32)*(word_len-1)); | |
332 | bits[word_len-1] &= ~last_mask; | |
333 | } | |
334 | } | |
335 | else | |
336 | { | |
337 | size_t i; | |
338 | for (i = 0; i < len; i++) | |
339 | scm_array_handle_set (&handle, i*inc, val); | |
340 | } | |
341 | ||
342 | scm_array_handle_release (&handle); | |
343 | ||
344 | return SCM_UNSPECIFIED; | |
345 | } | |
346 | #undef FUNC_NAME | |
347 | ||
348 | SCM_DEFINE (scm_list_to_bitvector, "list->bitvector", 1, 0, 0, | |
349 | (SCM list), | |
350 | "Return a new bitvector initialized with the elements\n" | |
351 | "of @var{list}.") | |
352 | #define FUNC_NAME s_scm_list_to_bitvector | |
353 | { | |
354 | size_t bit_len = scm_to_size_t (scm_length (list)); | |
355 | SCM vec = scm_c_make_bitvector (bit_len, SCM_UNDEFINED); | |
356 | size_t word_len = (bit_len+31)/32; | |
357 | scm_t_array_handle handle; | |
358 | scm_t_uint32 *bits = scm_bitvector_writable_elements (vec, &handle, | |
359 | NULL, NULL, NULL); | |
360 | size_t i, j; | |
361 | ||
362 | for (i = 0; i < word_len && scm_is_pair (list); i++, bit_len -= 32) | |
363 | { | |
364 | scm_t_uint32 mask = 1; | |
365 | bits[i] = 0; | |
366 | for (j = 0; j < 32 && j < bit_len; | |
367 | j++, mask <<= 1, list = SCM_CDR (list)) | |
368 | if (scm_is_true (SCM_CAR (list))) | |
369 | bits[i] |= mask; | |
370 | } | |
371 | ||
372 | scm_array_handle_release (&handle); | |
373 | ||
374 | return vec; | |
375 | } | |
376 | #undef FUNC_NAME | |
377 | ||
378 | SCM_DEFINE (scm_bitvector_to_list, "bitvector->list", 1, 0, 0, | |
379 | (SCM vec), | |
380 | "Return a new list initialized with the elements\n" | |
381 | "of the bitvector @var{vec}.") | |
382 | #define FUNC_NAME s_scm_bitvector_to_list | |
383 | { | |
384 | scm_t_array_handle handle; | |
385 | size_t off, len; | |
386 | ssize_t inc; | |
387 | scm_t_uint32 *bits; | |
388 | SCM res = SCM_EOL; | |
389 | ||
390 | bits = scm_bitvector_writable_elements (vec, &handle, | |
391 | &off, &len, &inc); | |
392 | ||
393 | if (off == 0 && inc == 1) | |
394 | { | |
395 | /* the usual case | |
396 | */ | |
397 | size_t word_len = (len + 31) / 32; | |
398 | size_t i, j; | |
399 | ||
400 | for (i = 0; i < word_len; i++, len -= 32) | |
401 | { | |
402 | scm_t_uint32 mask = 1; | |
403 | for (j = 0; j < 32 && j < len; j++, mask <<= 1) | |
404 | res = scm_cons ((bits[i] & mask)? SCM_BOOL_T : SCM_BOOL_F, res); | |
405 | } | |
406 | } | |
407 | else | |
408 | { | |
409 | size_t i; | |
410 | for (i = 0; i < len; i++) | |
411 | res = scm_cons (scm_array_handle_ref (&handle, i*inc), res); | |
412 | } | |
413 | ||
414 | scm_array_handle_release (&handle); | |
415 | ||
416 | return scm_reverse_x (res, SCM_EOL); | |
417 | } | |
418 | #undef FUNC_NAME | |
419 | ||
420 | /* From mmix-arith.w by Knuth. | |
421 | ||
422 | Here's a fun way to count the number of bits in a tetrabyte. | |
423 | ||
424 | [This classical trick is called the ``Gillies--Miller method for | |
425 | sideways addition'' in {\sl The Preparation of Programs for an | |
426 | Electronic Digital Computer\/} by Wilkes, Wheeler, and Gill, second | |
427 | edition (Reading, Mass.:\ Addison--Wesley, 1957), 191--193. Some of | |
428 | the tricks used here were suggested by Balbir Singh, Peter | |
429 | Rossmanith, and Stefan Schwoon.] | |
430 | */ | |
431 | ||
432 | static size_t | |
433 | count_ones (scm_t_uint32 x) | |
434 | { | |
435 | x=x-((x>>1)&0x55555555); | |
436 | x=(x&0x33333333)+((x>>2)&0x33333333); | |
437 | x=(x+(x>>4))&0x0f0f0f0f; | |
438 | x=x+(x>>8); | |
439 | return (x+(x>>16)) & 0xff; | |
440 | } | |
441 | ||
442 | SCM_DEFINE (scm_bit_count, "bit-count", 2, 0, 0, | |
443 | (SCM b, SCM bitvector), | |
444 | "Return the number of occurrences of the boolean @var{b} in\n" | |
445 | "@var{bitvector}.") | |
446 | #define FUNC_NAME s_scm_bit_count | |
447 | { | |
448 | scm_t_array_handle handle; | |
449 | size_t off, len; | |
450 | ssize_t inc; | |
451 | scm_t_uint32 *bits; | |
452 | int bit = scm_to_bool (b); | |
453 | size_t count = 0; | |
454 | ||
455 | bits = scm_bitvector_writable_elements (bitvector, &handle, | |
456 | &off, &len, &inc); | |
457 | ||
458 | if (off == 0 && inc == 1 && len > 0) | |
459 | { | |
460 | /* the usual case | |
461 | */ | |
462 | size_t word_len = (len + 31) / 32; | |
463 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - len); | |
464 | size_t i; | |
465 | ||
466 | for (i = 0; i < word_len-1; i++) | |
467 | count += count_ones (bits[i]); | |
468 | count += count_ones (bits[i] & last_mask); | |
469 | } | |
470 | else | |
471 | { | |
472 | size_t i; | |
473 | for (i = 0; i < len; i++) | |
474 | if (scm_is_true (scm_array_handle_ref (&handle, i*inc))) | |
475 | count++; | |
476 | } | |
477 | ||
478 | scm_array_handle_release (&handle); | |
479 | ||
480 | return scm_from_size_t (bit? count : len-count); | |
481 | } | |
482 | #undef FUNC_NAME | |
483 | ||
484 | /* returns 32 for x == 0. | |
485 | */ | |
486 | static size_t | |
487 | find_first_one (scm_t_uint32 x) | |
488 | { | |
489 | size_t pos = 0; | |
490 | /* do a binary search in x. */ | |
491 | if ((x & 0xFFFF) == 0) | |
492 | x >>= 16, pos += 16; | |
493 | if ((x & 0xFF) == 0) | |
494 | x >>= 8, pos += 8; | |
495 | if ((x & 0xF) == 0) | |
496 | x >>= 4, pos += 4; | |
497 | if ((x & 0x3) == 0) | |
498 | x >>= 2, pos += 2; | |
499 | if ((x & 0x1) == 0) | |
500 | pos += 1; | |
501 | return pos; | |
502 | } | |
503 | ||
504 | SCM_DEFINE (scm_bit_position, "bit-position", 3, 0, 0, | |
505 | (SCM item, SCM v, SCM k), | |
506 | "Return the index of the first occurrance of @var{item} in bit\n" | |
507 | "vector @var{v}, starting from @var{k}. If there is no\n" | |
508 | "@var{item} entry between @var{k} and the end of\n" | |
509 | "@var{bitvector}, then return @code{#f}. For example,\n" | |
510 | "\n" | |
511 | "@example\n" | |
512 | "(bit-position #t #*000101 0) @result{} 3\n" | |
513 | "(bit-position #f #*0001111 3) @result{} #f\n" | |
514 | "@end example") | |
515 | #define FUNC_NAME s_scm_bit_position | |
516 | { | |
517 | scm_t_array_handle handle; | |
518 | size_t off, len, first_bit; | |
519 | ssize_t inc; | |
520 | const scm_t_uint32 *bits; | |
521 | int bit = scm_to_bool (item); | |
522 | SCM res = SCM_BOOL_F; | |
523 | ||
524 | bits = scm_bitvector_elements (v, &handle, &off, &len, &inc); | |
525 | first_bit = scm_to_unsigned_integer (k, 0, len); | |
526 | ||
527 | if (off == 0 && inc == 1 && len > 0) | |
528 | { | |
529 | size_t i, word_len = (len + 31) / 32; | |
530 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - len); | |
531 | size_t first_word = first_bit / 32; | |
532 | scm_t_uint32 first_mask = | |
533 | ((scm_t_uint32)-1) << (first_bit - 32*first_word); | |
534 | scm_t_uint32 w; | |
535 | ||
536 | for (i = first_word; i < word_len; i++) | |
537 | { | |
538 | w = (bit? bits[i] : ~bits[i]); | |
539 | if (i == first_word) | |
540 | w &= first_mask; | |
541 | if (i == word_len-1) | |
542 | w &= last_mask; | |
543 | if (w) | |
544 | { | |
545 | res = scm_from_size_t (32*i + find_first_one (w)); | |
546 | break; | |
547 | } | |
548 | } | |
549 | } | |
550 | else | |
551 | { | |
552 | size_t i; | |
553 | for (i = first_bit; i < len; i++) | |
554 | { | |
555 | SCM elt = scm_array_handle_ref (&handle, i*inc); | |
556 | if ((bit && scm_is_true (elt)) || (!bit && scm_is_false (elt))) | |
557 | { | |
558 | res = scm_from_size_t (i); | |
559 | break; | |
560 | } | |
561 | } | |
562 | } | |
563 | ||
564 | scm_array_handle_release (&handle); | |
565 | ||
566 | return res; | |
567 | } | |
568 | #undef FUNC_NAME | |
569 | ||
570 | SCM_DEFINE (scm_bit_set_star_x, "bit-set*!", 3, 0, 0, | |
571 | (SCM v, SCM kv, SCM obj), | |
572 | "Set entries of bit vector @var{v} to @var{obj}, with @var{kv}\n" | |
573 | "selecting the entries to change. The return value is\n" | |
574 | "unspecified.\n" | |
575 | "\n" | |
576 | "If @var{kv} is a bit vector, then those entries where it has\n" | |
577 | "@code{#t} are the ones in @var{v} which are set to @var{obj}.\n" | |
578 | "@var{kv} and @var{v} must be the same length. When @var{obj}\n" | |
579 | "is @code{#t} it's like @var{kv} is OR'ed into @var{v}. Or when\n" | |
580 | "@var{obj} is @code{#f} it can be seen as an ANDNOT.\n" | |
581 | "\n" | |
582 | "@example\n" | |
583 | "(define bv #*01000010)\n" | |
584 | "(bit-set*! bv #*10010001 #t)\n" | |
585 | "bv\n" | |
586 | "@result{} #*11010011\n" | |
587 | "@end example\n" | |
588 | "\n" | |
589 | "If @var{kv} is a u32vector, then its elements are\n" | |
590 | "indices into @var{v} which are set to @var{obj}.\n" | |
591 | "\n" | |
592 | "@example\n" | |
593 | "(define bv #*01000010)\n" | |
594 | "(bit-set*! bv #u32(5 2 7) #t)\n" | |
595 | "bv\n" | |
596 | "@result{} #*01100111\n" | |
597 | "@end example") | |
598 | #define FUNC_NAME s_scm_bit_set_star_x | |
599 | { | |
600 | scm_t_array_handle v_handle; | |
601 | size_t v_off, v_len; | |
602 | ssize_t v_inc; | |
603 | scm_t_uint32 *v_bits; | |
604 | int bit; | |
605 | ||
606 | /* Validate that OBJ is a boolean so this is done even if we don't | |
607 | need BIT. | |
608 | */ | |
609 | bit = scm_to_bool (obj); | |
610 | ||
611 | v_bits = scm_bitvector_writable_elements (v, &v_handle, | |
612 | &v_off, &v_len, &v_inc); | |
613 | ||
614 | if (scm_is_bitvector (kv)) | |
615 | { | |
616 | scm_t_array_handle kv_handle; | |
617 | size_t kv_off, kv_len; | |
618 | ssize_t kv_inc; | |
619 | const scm_t_uint32 *kv_bits; | |
620 | ||
621 | kv_bits = scm_bitvector_elements (v, &kv_handle, | |
622 | &kv_off, &kv_len, &kv_inc); | |
623 | ||
624 | if (v_len != kv_len) | |
625 | scm_misc_error (NULL, | |
626 | "bit vectors must have equal length", | |
627 | SCM_EOL); | |
628 | ||
629 | if (v_off == 0 && v_inc == 1 && kv_off == 0 && kv_inc == 1 && kv_len > 0) | |
630 | { | |
631 | size_t word_len = (kv_len + 31) / 32; | |
632 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - kv_len); | |
633 | size_t i; | |
634 | ||
635 | if (bit == 0) | |
636 | { | |
637 | for (i = 0; i < word_len-1; i++) | |
638 | v_bits[i] &= ~kv_bits[i]; | |
639 | v_bits[i] &= ~(kv_bits[i] & last_mask); | |
640 | } | |
641 | else | |
642 | { | |
643 | for (i = 0; i < word_len-1; i++) | |
644 | v_bits[i] |= kv_bits[i]; | |
645 | v_bits[i] |= kv_bits[i] & last_mask; | |
646 | } | |
647 | } | |
648 | else | |
649 | { | |
650 | size_t i; | |
651 | for (i = 0; i < kv_len; i++) | |
652 | if (scm_is_true (scm_array_handle_ref (&kv_handle, i*kv_inc))) | |
653 | scm_array_handle_set (&v_handle, i*v_inc, obj); | |
654 | } | |
655 | ||
656 | scm_array_handle_release (&kv_handle); | |
657 | ||
658 | } | |
659 | else if (scm_is_true (scm_u32vector_p (kv))) | |
660 | { | |
661 | scm_t_array_handle kv_handle; | |
662 | size_t i, kv_len; | |
663 | ssize_t kv_inc; | |
664 | const scm_t_uint32 *kv_elts; | |
665 | ||
666 | kv_elts = scm_u32vector_elements (kv, &kv_handle, &kv_len, &kv_inc); | |
667 | for (i = 0; i < kv_len; i++, kv_elts += kv_inc) | |
668 | scm_array_handle_set (&v_handle, (*kv_elts)*v_inc, obj); | |
669 | ||
670 | scm_array_handle_release (&kv_handle); | |
671 | } | |
672 | else | |
673 | scm_wrong_type_arg_msg (NULL, 0, kv, "bitvector or u32vector"); | |
674 | ||
675 | scm_array_handle_release (&v_handle); | |
676 | ||
677 | return SCM_UNSPECIFIED; | |
678 | } | |
679 | #undef FUNC_NAME | |
680 | ||
681 | ||
682 | SCM_DEFINE (scm_bit_count_star, "bit-count*", 3, 0, 0, | |
683 | (SCM v, SCM kv, SCM obj), | |
684 | "Return a count of how many entries in bit vector @var{v} are\n" | |
685 | "equal to @var{obj}, with @var{kv} selecting the entries to\n" | |
686 | "consider.\n" | |
687 | "\n" | |
688 | "If @var{kv} is a bit vector, then those entries where it has\n" | |
689 | "@code{#t} are the ones in @var{v} which are considered.\n" | |
690 | "@var{kv} and @var{v} must be the same length.\n" | |
691 | "\n" | |
692 | "If @var{kv} is a u32vector, then it contains\n" | |
693 | "the indexes in @var{v} to consider.\n" | |
694 | "\n" | |
695 | "For example,\n" | |
696 | "\n" | |
697 | "@example\n" | |
698 | "(bit-count* #*01110111 #*11001101 #t) @result{} 3\n" | |
699 | "(bit-count* #*01110111 #u32(7 0 4) #f) @result{} 2\n" | |
700 | "@end example") | |
701 | #define FUNC_NAME s_scm_bit_count_star | |
702 | { | |
703 | scm_t_array_handle v_handle; | |
704 | size_t v_off, v_len; | |
705 | ssize_t v_inc; | |
706 | const scm_t_uint32 *v_bits; | |
707 | size_t count = 0; | |
708 | int bit; | |
709 | ||
710 | /* Validate that OBJ is a boolean so this is done even if we don't | |
711 | need BIT. | |
712 | */ | |
713 | bit = scm_to_bool (obj); | |
714 | ||
715 | v_bits = scm_bitvector_elements (v, &v_handle, | |
716 | &v_off, &v_len, &v_inc); | |
717 | ||
718 | if (scm_is_bitvector (kv)) | |
719 | { | |
720 | scm_t_array_handle kv_handle; | |
721 | size_t kv_off, kv_len; | |
722 | ssize_t kv_inc; | |
723 | const scm_t_uint32 *kv_bits; | |
724 | ||
725 | kv_bits = scm_bitvector_elements (v, &kv_handle, | |
726 | &kv_off, &kv_len, &kv_inc); | |
727 | ||
728 | if (v_len != kv_len) | |
729 | scm_misc_error (NULL, | |
730 | "bit vectors must have equal length", | |
731 | SCM_EOL); | |
732 | ||
733 | if (v_off == 0 && v_inc == 1 && kv_off == 0 && kv_inc == 1 && kv_len > 0) | |
734 | { | |
735 | size_t i, word_len = (kv_len + 31) / 32; | |
736 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - kv_len); | |
737 | scm_t_uint32 xor_mask = bit? 0 : ((scm_t_uint32)-1); | |
738 | ||
739 | for (i = 0; i < word_len-1; i++) | |
740 | count += count_ones ((v_bits[i]^xor_mask) & kv_bits[i]); | |
741 | count += count_ones ((v_bits[i]^xor_mask) & kv_bits[i] & last_mask); | |
742 | } | |
743 | else | |
744 | { | |
745 | size_t i; | |
746 | for (i = 0; i < kv_len; i++) | |
747 | if (scm_is_true (scm_array_handle_ref (&kv_handle, i))) | |
748 | { | |
749 | SCM elt = scm_array_handle_ref (&v_handle, i*v_inc); | |
750 | if ((bit && scm_is_true (elt)) || (!bit && scm_is_false (elt))) | |
751 | count++; | |
752 | } | |
753 | } | |
754 | ||
755 | scm_array_handle_release (&kv_handle); | |
756 | ||
757 | } | |
758 | else if (scm_is_true (scm_u32vector_p (kv))) | |
759 | { | |
760 | scm_t_array_handle kv_handle; | |
761 | size_t i, kv_len; | |
762 | ssize_t kv_inc; | |
763 | const scm_t_uint32 *kv_elts; | |
764 | ||
765 | kv_elts = scm_u32vector_elements (kv, &kv_handle, &kv_len, &kv_inc); | |
766 | for (i = 0; i < kv_len; i++, kv_elts += kv_inc) | |
767 | { | |
768 | SCM elt = scm_array_handle_ref (&v_handle, (*kv_elts)*v_inc); | |
769 | if ((bit && scm_is_true (elt)) || (!bit && scm_is_false (elt))) | |
770 | count++; | |
771 | } | |
772 | ||
773 | scm_array_handle_release (&kv_handle); | |
774 | } | |
775 | else | |
776 | scm_wrong_type_arg_msg (NULL, 0, kv, "bitvector or u32vector"); | |
777 | ||
778 | scm_array_handle_release (&v_handle); | |
779 | ||
780 | return scm_from_size_t (count); | |
781 | } | |
782 | #undef FUNC_NAME | |
783 | ||
784 | SCM_DEFINE (scm_bit_invert_x, "bit-invert!", 1, 0, 0, | |
785 | (SCM v), | |
786 | "Modify the bit vector @var{v} by replacing each element with\n" | |
787 | "its negation.") | |
788 | #define FUNC_NAME s_scm_bit_invert_x | |
789 | { | |
790 | scm_t_array_handle handle; | |
791 | size_t off, len; | |
792 | ssize_t inc; | |
793 | scm_t_uint32 *bits; | |
794 | ||
795 | bits = scm_bitvector_writable_elements (v, &handle, &off, &len, &inc); | |
796 | ||
797 | if (off == 0 && inc == 1 && len > 0) | |
798 | { | |
799 | size_t word_len = (len + 31) / 32; | |
800 | scm_t_uint32 last_mask = ((scm_t_uint32)-1) >> (32*word_len - len); | |
801 | size_t i; | |
802 | ||
803 | for (i = 0; i < word_len-1; i++) | |
804 | bits[i] = ~bits[i]; | |
805 | bits[i] = bits[i] ^ last_mask; | |
806 | } | |
807 | else | |
808 | { | |
809 | size_t i; | |
810 | for (i = 0; i < len; i++) | |
811 | scm_array_handle_set (&handle, i*inc, | |
812 | scm_not (scm_array_handle_ref (&handle, i*inc))); | |
813 | } | |
814 | ||
815 | scm_array_handle_release (&handle); | |
816 | ||
817 | return SCM_UNSPECIFIED; | |
818 | } | |
819 | #undef FUNC_NAME | |
820 | ||
821 | ||
822 | SCM | |
823 | scm_istr2bve (SCM str) | |
824 | { | |
825 | scm_t_array_handle handle; | |
826 | size_t len = scm_i_string_length (str); | |
827 | SCM vec = scm_c_make_bitvector (len, SCM_UNDEFINED); | |
828 | SCM res = vec; | |
829 | ||
830 | scm_t_uint32 mask; | |
831 | size_t k, j; | |
832 | const char *c_str; | |
833 | scm_t_uint32 *data; | |
834 | ||
835 | data = scm_bitvector_writable_elements (vec, &handle, NULL, NULL, NULL); | |
836 | c_str = scm_i_string_chars (str); | |
837 | ||
838 | for (k = 0; k < (len + 31) / 32; k++) | |
839 | { | |
840 | data[k] = 0L; | |
841 | j = len - k * 32; | |
842 | if (j > 32) | |
843 | j = 32; | |
844 | for (mask = 1L; j--; mask <<= 1) | |
845 | switch (*c_str++) | |
846 | { | |
847 | case '0': | |
848 | break; | |
849 | case '1': | |
850 | data[k] |= mask; | |
851 | break; | |
852 | default: | |
853 | res = SCM_BOOL_F; | |
854 | goto exit; | |
855 | } | |
856 | } | |
857 | ||
858 | exit: | |
859 | scm_array_handle_release (&handle); | |
860 | scm_remember_upto_here_1 (str); | |
861 | return res; | |
862 | } | |
863 | ||
2a610be5 AW |
864 | /* FIXME: h->array should be h->vector */ |
865 | static SCM | |
866 | bitvector_handle_ref (scm_t_array_handle *h, size_t pos) | |
867 | { | |
868 | return scm_c_bitvector_ref (h->array, pos); | |
869 | } | |
870 | ||
871 | static void | |
872 | bitvector_handle_set (scm_t_array_handle *h, size_t pos, SCM val) | |
873 | { | |
874 | scm_c_bitvector_set_x (h->array, pos, val); | |
875 | } | |
876 | ||
877 | static void | |
878 | bitvector_get_handle (SCM bv, scm_t_array_handle *h) | |
879 | { | |
880 | h->array = bv; | |
881 | h->ndims = 1; | |
882 | h->dims = &h->dim0; | |
883 | h->dim0.lbnd = 0; | |
884 | h->dim0.ubnd = BITVECTOR_LENGTH (bv) - 1; | |
885 | h->dim0.inc = 1; | |
886 | h->element_type = SCM_ARRAY_ELEMENT_TYPE_BIT; | |
887 | h->elements = h->writable_elements = BITVECTOR_BITS (bv); | |
888 | } | |
889 | ||
890 | SCM_ARRAY_IMPLEMENTATION (scm_tc16_bitvector, 0xffff, | |
891 | bitvector_handle_ref, bitvector_handle_set, | |
892 | bitvector_get_handle); | |
f45eccff | 893 | SCM_VECTOR_IMPLEMENTATION (SCM_ARRAY_ELEMENT_TYPE_BIT, scm_make_bitvector); |
2a610be5 | 894 | |
cf396142 AW |
895 | void |
896 | scm_init_bitvectors () | |
897 | { | |
898 | scm_tc16_bitvector = scm_make_smob_type ("bitvector", 0); | |
899 | scm_set_smob_free (scm_tc16_bitvector, bitvector_free); | |
900 | scm_set_smob_print (scm_tc16_bitvector, bitvector_print); | |
901 | scm_set_smob_equalp (scm_tc16_bitvector, bitvector_equalp); | |
902 | ||
903 | #include "libguile/bitvectors.x" | |
904 | } | |
905 | ||
906 | /* | |
907 | Local Variables: | |
908 | c-file-style: "gnu" | |
909 | End: | |
910 | */ |