1 ;;;; This software is part of the SBCL system. See the README file for
4 ;;;; While most of SBCL is derived from the CMU CL system, the test
5 ;;;; files (like this one) were written from scratch after the fork
8 ;;;; This software is in the public domain and is provided with
9 ;;;; absolutely no warranty. See the COPYING and CREDITS files for
10 ;;;; more information.
12 ;;; the bitvector transforms were buggy prior to sbcl-0.7.3.4 under
13 ;;; speed-optimizing regimes; in particular, they would fail if the
14 ;;; vector length were near ARRAY-DIMENSION-LIMIT. Testing this takes
15 ;;; up a certain amount of time...
17 (declaim (optimize (speed 3) (safety 1) (space 0) (compilation-speed 0)))
19 (defun test-small-bit-vectors ()
20 ;; deal with the potential length 0 special case
21 (let ((a (make-array 0 :element-type
'bit
))
22 (b (make-array 0 :element-type
'bit
)))
23 (assert (equal (bit-not a
) #*))
24 (assert (equal (bit-xor a b a
) #*))
25 (assert (equal (bit-and a a b
) #*)))
26 ;; also test some return values for sanity
27 (let ((a (make-array 33 :element-type
'bit
:initial-element
0))
28 (b (make-array 33 :element-type
'bit
:initial-element
0)))
29 (assert (equal (bit-not a a
) #*111111111111111111111111111111111))
30 (setf (aref a
0) 0) ; a = #*011..1
31 (setf (aref b
1) 1) ; b = #*010..0
32 (assert (equal (bit-xor a b
) #*001111111111111111111111111111111))
33 (assert (equal (bit-and a b
) #*010000000000000000000000000000000)))
34 ;; a special COUNT transform on bitvectors; triggers on (>= SPEED SPACE)
36 (declare (optimize (speed 3) (space 1)))
37 (let ((bv1 (make-array 5 :element-type
'bit
))
38 (bv2 (make-array 0 :element-type
'bit
))
39 (bv3 (make-array 68 :element-type
'bit
)))
40 (declare (type simple-bit-vector bv1 bv2 bv3
))
41 (setf (sbit bv3
42) 1)
42 ;; bitvector smaller than the word size
43 (assert (= 0 (count 1 bv1
)))
44 (assert (= 5 (count 0 bv1
)))
45 ;; special case of 0-length bitvectors
46 (assert (= 0 (count 1 bv2
)))
47 (assert (= 0 (count 0 bv2
)))
48 ;; bitvector larger than the word size
49 (assert (= 1 (count 1 bv3
)))
50 (assert (= 67 (count 0 bv3
))))))
56 (defun test-big-bit-vectors ()
57 ;; now test the biggy, mostly that it works...
59 (inform :make-array-1
)
60 (make-array (1- array-dimension-limit
)
61 :element-type
'bit
:initial-element
0)))
63 (inform :make-array-2
)
64 (make-array (1- array-dimension-limit
)
65 :element-type
'bit
:initial-element
0))))
69 (assert (= (aref a
0) 1))
71 (assert (= (aref a
(- array-dimension-limit
2)) 1))
75 (assert (= (aref a
0) 0))
77 (assert (= (aref a
(- array-dimension-limit
2)) 0))))
79 (test-small-bit-vectors)
81 ;; except on machines where the arrays won't fit into the dynamic space.
82 #+#.
(cl:if
(cl:> (sb-ext:dynamic-space-size
)
83 (cl:truncate
(cl:1- cl
:array-dimension-limit
)
87 (test-big-bit-vectors)
89 (with-test (:name
:find-non-bit-from-bit-vector
)
90 (assert (not (find #\a #*0101)))
91 (assert (not (position #\a #*0101)))
92 (let ((f1 (compile nil
97 (position b
#*0101)))))
98 (assert (not (funcall f1 t
)))
99 (assert (not (funcall f2 t
))))
100 (let ((f1 (compile nil
102 (declare (bit-vector b
))
106 (declare (bit-vector b
))
108 (assert (not (funcall f1
#*010101)))
109 (assert (not (funcall f2
#*101010)))))
111 ;;; BIT-POSITION would access 1 word beyond a bit-vector's final word
112 ;;; which could crash if the next page of memory was not readable.
113 ;;; To produce such a sitution, create a bit-vector at the end of static space,
114 ;;; relying on the fact that there should be a gap to the following space.
115 ;;; (Indeed this test reliably crashed prior to the fix for overrun)
116 (with-test (:name
:bit-position-overrun
)
117 (let* ((n-bytes (* 4 sb-vm
:n-word-bytes
))
118 (addr (- sb-vm
:static-space-end n-bytes
))
119 (n-bits (* 2 sb-vm
:n-word-bits
)))
120 (setf (sb-sys:sap-ref-word
(sb-sys:int-sap addr
) 0) sb-vm
:simple-bit-vector-widetag
)
121 (setf (sb-sys:sap-ref-word
(sb-sys:int-sap addr
) sb-vm
:n-word-bytes
)
122 (ash n-bits sb-vm
:n-fixnum-tag-bits
))
123 (multiple-value-bind (object widetag size
)
124 (sb-vm::reconstitute-object
(ash addr
(- sb-vm
:n-fixnum-tag-bits
)))
125 (declare (ignore widetag
))
126 (assert (simple-bit-vector-p object
))
127 (assert (= size n-bytes
))
128 (assert (not (sb-kernel:%bit-position
/1 object nil
0 n-bits
))))))