Эффективный isalnum()

Кто нибуть писал что нибуть своё ?
Я написал процедуру которая устанавливает флаг нуля если символ попадает в диапазон: 2Dh,2eh,30h-39h,41h-5ah,5fh,61h-7ah. Получает байт для проверки в al, использует только ah + флаги. Нужна максимальная скорость выполнения и минимальный размер.

Код (Text):

1. vsumbol:
2.             cmp al,41h
3.             jbe .s_low         
4.             cmp al,5fh
5.             jbe .s_hlow
6.             mov ah,61h
7. @@:         cmp ah,al
8.             jz .s_equ
9.             inc ah
10.             cmp ah,7ah
11.             jbe @b
12.             jmp .s_equ                     
13. .s_hlow:            jz .s_equ
14.             mov ah,42h
15. @@:         cmp ah,al
16.             jz .s_equ
17.             inc ah
18.             cmp ah,5ah
19.             jbe @b
20.             jmp .s_equ                     
21. .s_low:             jz .s_equ
22.             cmp al,2eh
23.             jz .s_equ
24.             cmp al,2dh
25.             jz .s_equ
26.             jb .s_equ
27.             mov ah,30h
28. @@:         cmp ah,al
29.             jz .s_equ
30.             inc ah
31.             cmp ah,39
32.             jbe @b
33.            
34. .s_equ:     ret

 

А зачем там два цикла?

Код (Text):

1. ; ------------------------------------------------------------
2. ; Input:
3. ;   AL = character
4. ; Output:
5. ;   CF=TRUE if character is in alpha-numeric range
6. ; ------------------------------------------------------------
7. isalnum:
8.     cmp al, '0'
9.     jb  .not_alpha_num
10.     cmp al, '9'
11.     jbe .digit
12.  
13.     cmp al, 'A'
14.     jb  .not_alpha_num
15.     cmp al, 'Z'
16.     jbe .upper_case
17.  
18.     cmp al, 'a'
19.     jb  .not_alpha_num
20.     cmp al, 'z'
21.     jbe .lower_case
22.  
23. .not_alpha_num:
24.     clc
25.     ret
26.  
27. .digit:
28. .upper_case:
29. .lower_case:
30.     stc
31.     ret

Код не тестировался, просто из головы...

 

ага точно, ступил что то...
вот без циклов:

Код (Text):

1. vsumbol:
2.             cmp al,41h
3.             jbe .s_low         
4.             cmp al,5fh
5.             jbe .s_hlow
6.             cmp al,61h
7.             jb .s_equ
8.             cmp al,7ah
9.             ja .s_equ
10.             cmp al,al
11.             jmp .s_equ
12. .s_hlow:            jz .s_equ
13.             cmp al,42h
14.             jb .s_equ
15.             cmp al,5ah
16.             ja .s_equ
17.             cmp al,al
18.             jmp .s_equ
19. .s_low:             jz .s_equ
20.             cmp al,2eh
21.             jz .s_equ
22.             cmp al,2dh
23.             jz .s_equ
24.             jb .s_equ          
25.             cmp al,30h
26.             jb .s_equ          
27.             cmp al,39h
28.             ja .s_equ
29.             cmp al,al
30.        
31. .s_equ:     ret

Вся идея была в том, чтобы не проверять весь диапазон если al=63h например, а начать сразу с 61h-7ah

 

Если нужен "эффективный" способ думаю стоит использовать таблицы

Код (Text):

1. ALPHA = 01h
2. DIGIT  = 02h
3. XDIGIT= 04h
4.  
5. ;    00  01  02  03  04  05  06  07  08  09  0A  0B  0C  0D  0E  0F
6. ;00:
7.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,08H,00H,00H,00H,08H,00H,00H
8. ;10:
9.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
10. ;20:
11.  DB  08H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
12. ;30: '0' '1' '2' '3' '4' '5' '6' '7' '8' '9'
13.  DB  06H,06H,06H,06H,06H,06H,06H,06H,06H,06H,00H,00H,00H,00H,00H,00H
14. ;40:     'A' 'B' 'C' 'D' 'E' 'F'
15.  DB  00H,05H,05H,05H,05H,05H,05H,01H,01H,01H,01H,01H,01H,01H,01H,01H
16. ;50:                                         'Z'
17.  DB  01H,01H,01H,01H,01H,01H,01H,01H,01H,01H,01H,00H,00H,00H,00H,00H
18. ;60:     'a' 'b' 'c' 'd' 'e' 'f'
19.  DB  00H,05H,05H,05H,05H,05H,05H,01H,01H,01H,01H,01H,01H,01H,01H,01H
20. ;70:                                         'z'
21.  DB  01H,01H,01H,01H,01H,01H,01H,01H,01H,01H,01H,00H,00H,00H,00H,00H
22. ;80
23.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
24. ;90
25.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
26. ;A0
27.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
28. ;B0
29.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
30. ;C0
31.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
32. ;D0
33.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
34. ;E0
35.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H
36. ;F0
37.  DB  00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H,00H

 

Обычно это взаимоисключающие параметры кода.
Если использовать таблицу, её незачем делать размером 256 байт. Достаточно 77 байт таблицы. Будет быстрее грузиться в кэш.

Код (Text):

1. .data
2. table           db  0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1
3.                 db  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
4.                 db  0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0
5.                 db  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  
6. .code
7.     cmp     al,7Ah
8.     jge     _end
9.     sub     al,2Dh
10.     js      _end
11.     and     eax,0FFh
12.     mov     eax,[eax+offset table]
13.     test    al,al
14.  _end:

 

немного побольше теории про таблицы можно ? что то не въеду ни как...

 

Нас интересует конкретно 78 возможных значений al (от 2Dh до 7ah включительно). Если за пределами этого диапазона, то однозначно флаг ZF должен быть сброшен. Если внутри диапазона - состояние флага будет зависеть от содержимого al: либо установлен, либо сброшен. Проще всего установить или сбросить флаг сделав test al,al. Если нужно установить ZF, то содержимое al перед выполнением test должно быть ==0. Если нужно сбросить ZF - любое !=0 (например 1). Проще всего установить требуемое al путем загрузки в него того или иного значения из таблицы. Причем сам регистр al (его содержимое) будет управлять тем, какое число в al будет загружено из таблицы: 0 или 1.
Таблица составлена таким образом, что первой её ячейке соответствует значение al, которое должно быть загружено в регистр перед выполнением test al,al при его исходном значении равном 2Dh, вторая ячейка содержит значение, которое должно быть загружено при исходном al==2Eh и т.д. до 7Ah.
теперь так:

Код (Text):

1.    
2.     cmp     al,7Ah
3.     ;если al больше или равно 7ah, то cmp установит ZF (если равно 7Ah)
4.     ;или сбросит ZF, если число больше 7Ah (за пределами интересующего диапазона).
5.     ;и после этого - сразу на _end.
6.     jge     _end
7.     ;если меньше, проверяем теперь на нижнюю границу: 2Dh,
8.     ;заодно меняем al на значение равное смещению от нижней границы
9.     ;путём вычитания этой границы (2Dh)
10.     sub     al,2Dh
11.     ;если после вычитания число получилось меньше 0, то ZF будет сброшен (al было меньше чем 2Dh)
12.     ;если после вычитания число получилось равно 0, то ZF будет установлен (al был равен 2Dh)
13.     ;если любое из этих двух условий выполнено - значит состояние ZF соответствует входным данным
14.     ;и теперь на выход.
15.     jle      _end
16.     ;тут оказываемся, если исходный al был больше 2D и меньше 7A
17.     ;после sub в al могут быть значения от 0 до (7A-2D)
18.     ;то, что содержится сейчас в al - это смещение от начала исходного диапазона
19.     ;интересующих значений (от 2Ah). Т.е. если al==5, исходный al был 32h (2D+5)
20.     ;теперь имея смещение относительно начала диапазона, будем брать из таблицы
21.     ;значения, находящиеся в ней по этому смещению.
22.     ;обнуляем старшие разряды eax(кроме al)
23.     and     eax,0FFh
24.     ;значение eax+offset table теперь равно адресу ячейки в таблице, из которой
25.     ;нужно загрузить число в al.
26.     ;Грузим al из таблицы (либо 0, либо 1)
27.     mov     al,byte ptr[eax+offset table]
28.     ;делаем test, чтобы установить ZF в зависимости от того что было в al: 0 или 1
29.     test    al,al
30.  _end:

Вроде всё.
Т.е получается, что первыми двумя условными переходами отсекаются значения за пределами диапазона 2D - 7A, а затем регистру al сопоставляется то или иное число из таблицы, которое при выполнении test даст нужное состояние флага ZF.
Рассказчик правда из меня неважный

 

2cresta ого..., спасибо большое, всё понял, теперь буду использовать, рассказчик из тебя отличный
всем спасибо.

 

Можно ужать таблицу. использовав биты. а не байты. соответственно добавится shl/bt

 

cresta

А мне нравится, не нужно ни call на подпрограму, ни макромос для проверки, и всегда легко изменить настройки таблицы например добавить символы '_','$','@','%' в диапазон идентификаторов.
Если обнулить eax, а код хранить в al, символы проверять очень просто.

Код (Text):

1. xor eax,eax
2. mov esi,string
3. lodsb
4. test [eax+char_table],ALNUM
5. jxx L_ALNUM
6. test [eax+char_table],SPACE
7. jxx L_SPACE
8. or [eax+char_table],0
9. jz L_INVALID

А если еще и на граничу 256 выровнять то можно вообще для проверки использовать только eax.

Код (Text):

1. align 256
2. char_table: ...
3. mov eax,char_table
4. mov esi,string
5. lodsb
6. test [eax],ALNUM
7. jxx

Но это больше относится вообше к разбору символов а не к данному случаю.

 

cresta
Очень неплохо!

 

h3uristic

Можно еще на 1 инструкцию ( и на 1 байт) подсократить код, если не грузать в al значение из таблицы, а непосредственно ячейку таблицы проверять:

Код (Text):

1.     cmp     al,7Ah
2.     jge     _end
3.     sub     al,2Dh
4.     jle     _end
5.     and     eax,0FFh
6.     cmp     byte ptr [eax+offset table],0
7.  _end:

Smile
В общем случае конечно, используется 256 байт, но тут такой случай, что весь диапазон не нужен.
Если делать таблицу 256 байт, то код вообще будет состоять из двух инструкций:

Код (Text):

1.     and     eax,0FFh
2.     cmp     byte ptr [eax+offset table],0

 

2cresta круто, но таблица огромная, 77 байт - памойму это много...
мне кажется, можно/нужно последовать совету n0name и использовать не байты, а биты как одну ячейку.
Вот первое что пришло в голову, буду переделывать...

Код (Text):

1. ;; Только уже во флаге переноса возвращается результат
2. ;; если CF = 1 значит число входит в заданный диапазон
3. vsumbol:
4. ;;
5. ;;;;;;; ?????????????????????
6. ;;          cmp al,7ah
7.             ja @f
8.             sub al,2dh
9.             js @f
10. ;;;;;;; ?????????????????????      
11.             and eax,0ffh
12.             push eax
13.             shr eax,3
14.             mov bl, [ table + eax ]
15.             shl eax,3
16.             sub [esp],eax
17.             pop eax
18.             bt ebx,eax
19.             jmp .exit
20.  
21. @@:             or al,al   
22. .exit:              ret
23.            
24.            
25. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
26. ;;
27. ;;;;;;;;;;2dh-7ah
28. table       db      11111011b, 00011111b, 11110000b, 11111111b  ;   2dh - 4ch
29.         db      11111111b, 01111111b, 11101000b, 11111111b  ;   4dh - 6ch
30.         db      11111111b, 11111111b                    ;       6dh - 7ch

 

IMHO команды BOUND и XLAT никто не отменял

 

h3uristic
Этот код работает неправильно: для 5ah и 5Bh он выдает одинаковый результат на выходе, хотя должен разный.
Да и медленее он в 3 раза. И регистр ebx задействуется, необходимо его сохранять и восстанавливать (push/pop)
А сэкономить места удается совсем немного: 79 байт (40 таблица+39 код) против 97 (77 таблица+20 код).
Стоит 19 байт трехкратного снижения в скорости? Если код с битовой таблицей привести в рабочий вид, возможно от этих 19 байт экономии ничего не останется. ИМХО.

Mikl__
Думаю, xlat будет медленее, к тому же требуется 256 байт таблица

 

где ты 40 насчитал? 10 в 2 раза меньше.

 

2cresta код работает правильно, ошибка в таблице нашлась, как раз с 5bh :/... и всё таки мне кажется, что можно что нибуть придумать...

Код (Text):

1. ;это правильная таблица
2. table       db      11111011b, 00011111b, 11110000b, 11111111b      ;   2dh - 4ch
3.         db      11111111b, 00111111b, 11110100b, 11111111b      ;   4dh - 6ch
4.         db      11111111b, 11111111b                        ;       6dh - 7ch

 

n0name
да, точно. Только битовая работа - не самы лучший вариант.

h3uristic
Ага ошибки нет, вот только скорость работы с битовой таблицей не впечатляет. По-прежнему в 3 раза медленее (на 10 проходах 140 тиков против 48), чем с байтовой. Впрочем я уже говорил, что это взаимоисключающие вещи: размер и скорость. Выбери что-то либо скорость либо размер.
Битовая таблица вынуждает применять операции сдвига, запоминания промежуточных данных, их восстановления. и при этом теряется основное преимущество таблицы - мгновенное получение готового результата. Одни минусы. Даже тупое сканирование, например:

Код (Text):

1.      _st:      
2.             cmp     al,2dh
3.             je      _set
4.             cmp     al,2eh
5.             je      _set
6.             cmp     al,5fh
7.             je      _set
8.             cmp     al,7ah
9.             jge     _reset
10.             cmp     al,61h
11.             jge     _set
12.             cmp     al,5ah
13.             jg      _reset
14.             cmp     al,41h
15.             jge     _set
16.             cmp     al,39h
17.             jg      _reset
18.             cmp     al,30h
19.             jge     _set
20.            
21.            
22.  _reset:    or      al,-1
23.             test    al,al
24.             jmp     _end          
25.    _set:
26.             xor     al,al
27.             test    al,al        
28.    _end:

быстрее в 2 раза, чем побитовая работа. К тому же и размер при тупом сканировании меньше В общем, самый неудачный вариант.

Посмотри в аттаче, как распределяется скорость работы в зависимости от размера кода.

 

что-то не приаттачилось.
Ещё одна попытка.

 

cresta
ну для такой задачи обычно ставится приоритет в размер кода, а не в скорость работы.