| 1 |
;;; |
| 2 |
;;; text.unicode.codeset - Set of character codes |
| 3 |
;;; |
| 4 |
;;; Originally written by Shiro Kawai, 2011 |
| 5 |
;;; Public Domain - use as you like. |
| 6 |
;;; |
| 7 |
|
| 8 |
;; This module provides char-code-set, a set of character codepoints. |
| 9 |
;; Internally it is kept in a bitmap and a collection of character code |
| 10 |
;; ranges, just like the built-in <char-set>. |
| 11 |
;; |
| 12 |
;; We need this instead of built-in <char-set> to generate character |
| 13 |
;; category tables. The internal <char-set> assumes characters |
| 14 |
;; are in native encoding, but for the code generation we have to deal |
| 15 |
;; with all supported encodings. |
| 16 |
|
| 17 |
(define-module text.unicode.codeset |
| 18 |
(export <char-code-set> |
| 19 |
add-code! |
| 20 |
add-code-range! |
| 21 |
code-set-union |
| 22 |
dump-code-set-in-C)) |
| 23 |
(select-module text.unicode.codeset) |
| 24 |
|
| 25 |
(define-constant SCM_CHAR_SET_SMALL_CHARS 128) |
| 26 |
|
| 27 |
;; <char-code-set> is for an intermediate structure to build <char-set> |
| 28 |
;; for each character categories. |
| 29 |
|
| 30 |
(define-class <char-code-set> () |
| 31 |
((name :init-keyword :name) |
| 32 |
(small-map :init-value 0) |
| 33 |
(large-map :init-form (make-tree-map)))) ;; integer : integer |
| 34 |
|
| 35 |
(define-method write-object ((cs <char-code-set>) out) |
| 36 |
(print (~ cs'name)) |
| 37 |
(do ([k 0 (+ k 32)]) |
| 38 |
[(>= k SCM_CHAR_SET_SMALL_CHARS)] |
| 39 |
(let1 word (ash (~ cs'small-map) (- k)) |
| 40 |
(format out "~a~8,'0b ~8,'0b ~8,'0b ~8,'0b~a" |
| 41 |
(if (zero? k) "[" " ") |
| 42 |
(logand (ash word -24) #xff) |
| 43 |
(logand (ash word -16) #xff) |
| 44 |
(logand (ash word -8) #xff) |
| 45 |
(logand (ash word 0) #xff) |
| 46 |
(if (>= k (- SCM_CHAR_SET_SMALL_CHARS 32)) "]" "\n")))) |
| 47 |
(dolist [r (tree-map->alist (~ cs'large-map))] |
| 48 |
(format out "\n~5,'0x-~5,'0x" (car r) (cdr r)))) |
| 49 |
|
| 50 |
(define-method add-code! ((cs <char-code-set>) code) |
| 51 |
(if (< code SCM_CHAR_SET_SMALL_CHARS) |
| 52 |
(set! (~ cs'small-map) (copy-bit code (~ cs'small-map) #t)) |
| 53 |
(receive (l0 h0) (tree-map-floor (~ cs'large-map) code) |
| 54 |
(receive (l1 h1) (tree-map-ceiling (~ cs'large-map) code) |
| 55 |
(cond [(and h0 l1 (= (+ h0 1) code) (= code (- l1 1))) |
| 56 |
;; merge two |
| 57 |
(tree-map-delete! (~ cs'large-map) l1) |
| 58 |
(tree-map-put! (~ cs'large-map) l0 h1)] |
| 59 |
[(and h0 (= (+ h0 1) code)) |
| 60 |
;; extend right |
| 61 |
(tree-map-put! (~ cs'large-map) l0 code)] |
| 62 |
[(and l1 (= code (- l1 1))) |
| 63 |
;; extend left |
| 64 |
(tree-map-delete! (~ cs'large-map) l1) |
| 65 |
(tree-map-put! (~ cs'large-map) code h1)] |
| 66 |
[(and l0 (<= code h0))] ;; already a member |
| 67 |
[else ;; island |
| 68 |
(tree-map-put! (~ cs'large-map) code code)]))))) |
| 69 |
|
| 70 |
;; START and END are both inclusive. |
| 71 |
(define-method add-code-range! ((cs <char-code-set>) start end) |
| 72 |
(when (< start SCM_CHAR_SET_SMALL_CHARS) |
| 73 |
(let1 e (min (+ end 1) SCM_CHAR_SET_SMALL_CHARS) |
| 74 |
(update! (~ cs'small-map) (cut copy-bit-field <> -1 start e)))) |
| 75 |
(when (<= SCM_CHAR_SET_SMALL_CHARS end) |
| 76 |
(let1 start (max SCM_CHAR_SET_SMALL_CHARS start) |
| 77 |
;; search overlapping range |
| 78 |
(receive (s0 e0) (tree-map-floor (~ cs'large-map) start) |
| 79 |
(if (and s0 (<= start (+ e0 1))) |
| 80 |
;; start<--------->end |
| 81 |
;; s0<----------->e0 |
| 82 |
(let loop ([s s0] |
| 83 |
[e e0]) |
| 84 |
(tree-map-delete! (~ cs'large-map) s) |
| 85 |
(receive (s1 e1) (tree-map-successor (~ cs'large-map) s) |
| 86 |
(if (and s1 (<= s1 (+ end 1))) |
| 87 |
(loop s1 (max e1 e)) |
| 88 |
(tree-map-put! (~ cs'large-map) s0 (max e end))))) |
| 89 |
(receive (s0 e0) (tree-map-ceiling (~ cs'large-map) start) |
| 90 |
(if (and s0 (<= s0 (+ end 1))) |
| 91 |
;; start<---------------->end |
| 92 |
;; s0<------------------>e0 |
| 93 |
(let loop ([s s0] |
| 94 |
[e e0]) |
| 95 |
(tree-map-delete! (~ cs'large-map) s) |
| 96 |
(receive (s1 e1) (tree-map-successor (~ cs'large-map) s) |
| 97 |
(if (and s1 (<= s1 (+ end 1))) |
| 98 |
(loop s1 (max e1 e)) |
| 99 |
(tree-map-put! (~ cs'large-map) start (max e end))))) |
| 100 |
;; no overlap |
| 101 |
(tree-map-put! (~ cs'large-map) start end)))))))) |
| 102 |
|
| 103 |
(define (code-set-union-2 name cs1 cs2) |
| 104 |
(rlet1 cs (make <char-code-set> :name name) |
| 105 |
(set! (~ cs'small-map) (logior (~ cs1'small-map) (~ cs2'small-map))) |
| 106 |
(tree-map-for-each (~ cs1'large-map) (cut add-code-range! cs <> <>)) |
| 107 |
(tree-map-for-each (~ cs2'large-map) (cut add-code-range! cs <> <>)))) |
| 108 |
|
| 109 |
(define (code-set-union name cs1 cs2 . css) |
| 110 |
(if (null? css) |
| 111 |
(code-set-union-2 name cs1 cs2) |
| 112 |
(apply code-set-union name (code-set-union-2 #f cs1 cs2) css))) |
| 113 |
|
| 114 |
;; Dump the set as static C code fragment to construct immutable charset. |
| 115 |
(define-method dump-code-set-in-C ((cs <char-code-set>)) |
| 116 |
(define name (~ cs'name)) |
| 117 |
(define (dump-bitmap bitmap word-size) |
| 118 |
(do ([k 0 (+ k word-size)]) |
| 119 |
[(>= k SCM_CHAR_SET_SMALL_CHARS)] |
| 120 |
(format #t " 0x~v,'0xul,\n" |
| 121 |
(/ word-size 4) |
| 122 |
(logand (ash bitmap (- k)) (- (expt 2 word-size) 1))))) |
| 123 |
(print #"static const ScmBits charset_~|name|_small[] = {") |
| 124 |
(print "#if SIZEOF_LONG == 4") |
| 125 |
(dump-bitmap (~ cs'small-map) 32) |
| 126 |
(print "#else") |
| 127 |
(dump-bitmap (~ cs'small-map) 64) |
| 128 |
(print "#endif") |
| 129 |
(print "};") |
| 130 |
(print #"static const uint32_t charset_~|name|_large[] = {") |
| 131 |
(dolist [p (tree-map->alist (~ cs'large-map))] |
| 132 |
(format #t " 0x~6,'0x,\n" (car p)) |
| 133 |
(format #t " 0x~6,'0x,\n" (cdr p))) |
| 134 |
(print "};") |
| 135 |
(print #"static ScmObj make_charset_~|name|()") |
| 136 |
(print "{") |
| 137 |
(print #" return Scm_MakeImmutableCharSet(charset_~|name|_small,") |
| 138 |
(print #" charset_~|name|_large,") |
| 139 |
(print #" ~(* 2 (tree-map-num-entries (~ cs'large-map))));") |
| 140 |
(print "}")) |