[Openmcl-devel] Re: [cl-ppcre-devel] cl-ppcre speedup

[Alan Ruttenberg]

On Dec 15, 2004, at 3:41 AM, Gary Byers wrote:

> I wonder if there's a clever way to inline CHAR-UPCASE/CHAR-DOWNCASE ?
> (There are obviously straightforward ways to do this; it's sometimes
> faster to do this via table lookup, but there may be ways to do this
> without conditional branches or memory references.)
>

You never have to change more than one bit

(loop for code from 0 below 256
    for char = (code-char code)
    for upcase-code = (char-code (char-upcase char))
    always (if (/= upcase-code code) (= #b100000 (logxor code 
upcase-code)) t))

T

If the top nibble isn't 6 or 7 then you don't change the bit

(remove-duplicates
  (loop for code from 0 below 256
     for char = (code-char code)
     for upcase-code = (char-code (char-upcase char))
     when (/= upcase-code code)
     collect (/ (logand #xf0 code) 16)))

(6 7)

You need to do a lookup of the bit for 32 cases

(loop for code from 0 below 256
    for char = (code-char code)
    for upcase-code = (char-code (char-upcase char))
    when (and (/= upcase-code code) (= (logand #xf0 code) #60)) sum 1)
15

(loop for code from 0 below 256
    for char = (code-char code)
    for upcase-code = (char-code (char-upcase char))
    when (and (/= upcase-code code) (= (logand #xf0 code) #x70)) sum 1)

11

I presume that the ifs aren't really conditionals but rather uses of a 
condition register value

(defun char-upcase-by-bits (char)
   (let ((code (char-code char)))
     (let* ((nochange (if (= #x60 (logand code #xe0)) 1 0))
	   (offset (if (= 0 (logand #x10 code)) 0 1))
	   (testbit (if (logbitp (logior (ash offset 4) (logand #xf code)) 
#b00000111111111111111111111111110) 1 0))
	   (flipper (ash (logand testbit nochange) 5)))
       (code-char (logxor flipper code)))))

seems to work:

(loop for code from 0 below 256 for char = (code-char code)
    always (eq (char-upcase-by-bits char) (char-upcase char)))

T

The question is, how few instructions can this be packed in to and 
whether it runs faster than the simpler memory lookup.