Вариант конвертирования строки символов в double / real8
посредством SIMD
.
В соответствии с x64 software conventions
будем считать что указатель на начало Числовой строки подлежащие конвертированию расположено в RCX
.
Будем использовать x64
битный код при x32
битной адресации. Такой способ адресации позволяет использовать преимущества обоих диалектов.
Будем использовать недокументированное соглашение о передаче / возврате из функции множественных параметров. Соглашение абсолютно зеркально соглашению x64 software conventions
за тем исключением что описывает правила размещения параметров при выходе из процедуры.
Для удобства работы со стеком создаем текстовую константу которая по сути выполняет роль имени (идентификатора) локальной переменной не определенного типа и "произвольного" размера:
; псевдонимы операндов #region
BUFF_STR equ esp - xmmword * 8
; #endregion
Для удобства работы с регистрами создаем блок текстовых констант которые по сути будут представлять собой имена переменных неопределенного типа и размером в двойное слово (DWORD
) илиINT
для тех кому более привычен синтаксис СРР
которые не имеют своего собственного отображения в памяти, а все время своего существования размещаются в регистре с которым они ассоциированы, при этом некоторые "переменны" являются по сути "объединениями" и размещаются в одних и тех же регистрах:
; псевдонимы регистров #region
FRS_CHAR equ eax ; первый символ целой части
DOT_CHAR equ FRS_CHAR ; символ точки
CUR_CHAR equ ecx ; текущий символ
HASH_EXP equ edx ; хеш экспоненты
HASH_STR equ r8d ; хеш строки символов
END_CHAR equ HASH_STR ; последний символ
N_Z_CHAR equ r9d ; символ не нулевого числа
OFF_CHAR equ N_Z_CHAR ; смешение дробной части
EXP_CHAR equ r10d ; первый символ экспоненты
EXP_NUMB equ EXP_CHAR ; десятичная экспонента
LEN_NUMB equ r11d ; длина значимой части
LEN_CELL equ LEN_NUMB ; длина целой части
HASH_MUL equ ebx ; значение экспоненты в десятичной системе
MANT_ARG equ r8 ; мантисса аргумент множителя
LOGB_ARG equ r9d ; порядок аргумента множителя
MANT_MUL equ r10 ; мантисса множителя
LOGB_MUL equ r11d ; порядок множителя
; #endregion
Создаем секцию вспомогательных констант, стоит отметить что самая "лучшая" секция данных это такая секция которая размещена а секции кода, то есть при любой возможности необходимо избегать создания вспомогательных констант и размещать их непосредственно в секции кода в аргументах содержащихся непосредственно в инструкциях, к сожалению SIMD
команды не допускают непосредственной размещения данных в инструкциях секции кода, что вынуждает создавать секцию данных:
.data ; #region
Xmm_SP byte 10h dup (20h)
Xmm_HT byte 10h dup (09h)
Xmm_CR byte 10h dup (0Dh)
Xmm_LF byte 10h dup (0Ah)
Xmm_SL byte 10h dup ('/')
Xmm_30 byte 10h dup ('0')
Xmm_39 byte 10h dup ('9')
Xmm_0001 word 8 dup (010Ah)
Xmm_0010 dword 4 dup (10064h)
Xmm_0100 qword 2 dup (100002710h)
Mask_001 byte 2Bh, 2Dh, 0, 0, 0, 0, 09h, 0Ah, 0Dh, 20h, 44h, 46h, 64h, 66h, 45h, 65h
Mul_0001 qword 0E8D4A51000h
string byte '923456781234567812.3e-248 '
; #endregion
Приступаем к разбору строки, ожидая что адрес первого символа расположен в регистре ECX
которому присвоен псевдоним CUR_CHAR
:
Уменьшаем указатель адрес первого символа в
CUR_CHAR
на длинуХММ
регистра.Увеличиваем указатель адрес первого символа в
CUR_CHAR
на длинуХММ
регистра.
; пропуск обобщенного пробела #region
sub CUR_CHAR, xmmword
@@: add CUR_CHAR, xmmword
В результате при первоначальном входе в цикл обработки обобщенного пробела указатель текущего символа будет установлен на начало строки, при последующих итерациях он будет сдвигаться на длину SIMD
регистра. Такой способ организации начала цикла, при котором инкремент расположен в начале цикла, позволяет значительно упростить выход из цикла сведя его к команде проверки условия и условному переходу. В противном случае при размещении команда инкремента и проверки условий в конце цикла эти инструкции конфликтовали бы в части изменения флагов процессора что избыточно усложнило бы выход из цикла.
Загружаем строку символов в
ХММ0
и копируем ее вХММ1
/ХММ2
/ХММ3
получая четыре копии строки.
Сравниваем четыре копии строки содержащиеся в регистрах с четырьмя строками размещенными в памяти, равномерно заполненными символами
"пробел"
/"табуляция"
/"возврат каретки"
/"новая строка"
Складываем полученные результаты в регистр
ХММ0
.
movdqu xmm0,[CUR_CHAR]
movdqa xmm1, xmm0
movdqa xmm2, xmm0
movdqa xmm3, xmm0
pcmpeqb xmm0, xmmword ptr Xmm_SP
pcmpeqb xmm1, xmmword ptr Xmm_HT
pcmpeqb xmm2, xmmword ptr Xmm_CR
pcmpeqb xmm3, xmmword ptr Xmm_LF
paddb xmm0, xmm1
paddb xmm0, xmm2
paddb xmm0, xmm3
В результате байты регистра ХММ0
равные любому из четырех символов обобщенного пробела принимают значение -1
а не равные 0
. Векторное сравнение позволяет многократно повысить скорость сканирования строки не только за счет параллельного сравнения но и за счет исключения множества условных переходов характерных для "классических" способов.
Устанавливаем все байты
ХММ1
в значение-1
сравнивая их с самими собой.Если в
ХММ0
отсутствуют байты отличные от символов обобщенного пробела устанавливаем флаг переносаCF=1
.Если флаг переноса
CF=1
возвращаемся в начало цикла
pcmpeqb xmm1, xmm1
ptest xmm0, xmm1
jc @b ; повторный пропуск обобщенного пробела
; #endregion
В результате сканирование строки продолжается до тех пор пока не будет найден символ отличный от обобщенного пробела. Скорость сканирования можно дополнительно увеличить если разместить строки равномерно заполненные символами "пробел"
/ "табуляция"
/ "возврат каретки"
/ "новая строка"
в старших регистрах SIMD
, но в соответствии с соглашением вызова х64
это потребует предварительно сохранить их значение в память, а при выходе из функции восстановить, что учитывая ожидаемое время сканирования в один проход будет не оправданно.
Копируем старшие биты всех байтов регистра
ХММ0
вFRS_CHAR
Инвертируем
FRS_CHAR
, теперь биты соответствующие символам не равных обобщенному пробелу установлен в значение1
Сканируем биты регистра
FRS_CHAR
от младшего к старшему в поиске первого бита установлено в значение1
, и результат равный номеру бита, помещаем в этот же регистр.Добавляем значение
FRS_CHAR
кCUR_CHAR
.
; позиция первого символа не пробела #region
pmovmskb FRS_CHAR, xmm0
not FRS_CHAR
bsf FRS_CHAR, FRS_CHAR
add CUR_CHAR, FRS_CHAR
; #endregion
В результате в CUR_CHAR
размещается указатель на первый символ отличный от обобщенного пробела.
Копируем первый символ отличный от обобщенного пробела в регистр
EAX
одновременно расширяя его до двойного словаУстанавливаем флаг нуля
ZF=1
если символ равен нулюЕсли флаг нуля
ZF=1
то выходим из функции вернув код ошибки:
; тест аварийного окончания строки #region
movzx eax, byte ptr[CUR_CHAR]
test al, al
jz ErrorExit ; обрыв строки
; #endregion
В результате если первый отличный от обобщенного пробела символ будет символом конца строки функция завершиться вернув код ошибки.
Сравниваем регистр
AL
с символом'+'
.Устанавливаем
AL
в значение1
если символ равен'+'
и0
при любом другом значении.Добавляем регистр
EAX
к региструCUR_CHAR
.
; проверка символа +/- #region
cmp al, '+'
setz al
add CUR_CHAR, eax
В результате если первый отличный от обобщенного пробела символ равен '+'
то позиция текущего символа будет смещена на следующий символ, во всех остальных случаях символ будет подвергнут повторному анализу.
Сравниваем текущий символ с символом
'-'
.Устанавливаем значение
AL
в1
если символ равен'-'
и0
при любом другом значении.Добавляем регистр
EAX
к региструCUR_CHAR
.Добавляем регистр
EAX
к региструESP
и вычитая из суммы двойное слово.
cmp byte ptr[CUR_CHAR], '-'
setz al
add CUR_CHAR, eax
add esp, eax
; #endregion
В результате если текущий символ равен '-'
то позиция текущего символа будет смещена на следующий символ, а значение регистра стека увеличено на 1
, во всех остальных случаях символ будет подвергнут повторному анализу, а значение регистра стека останется без изменений. Прямое изменение значения указателя стека ESP считается крайне опасным действием чреватым непредсказуемыми ошибками, но я практикую "агрессивный" подход и считаю что не бывает "плохого" или "хорошего" кода, бывают хорошие и плохи программисты, хорошие пишут так как будто никаких правил нет вообще но результат при этом такой как будто они соблюдают их все, а плохие они просто плохие.
Загружаем старшую часть Числа, со смешением на 16 символов от начала Числа, в
ХММ0
.Копируем старшую часть Числа в
ХММ1
иХММ2
.Сравниваем регистр
ХММ0
со строкой в памяти равномерно заполненной символами'9'
.Копируем регистр
ХММ0
в регистрХММ1
.
; сканирование символов Числовой строки #region
movdqu xmm0,[CUR_CHAR + xmmword]
movdqa xmm2, xmm0
movdqa xmm3, xmm0
pcmpgtb xmm0, xmmword ptr Xmm_39
movdqa xmm1, xmm0
В результат получаем две копии строки в которых все биты символы которых больше символа '9'
установлены в значение -1
, а все остальные в значение 0
.
Сравниваем регистр
ХММ2
со строкой в памяти равномерно заполненной символами"/"
.Сравниваем регистр
ХММ3
со строкой в памяти равномерно заполненной символами"0"
.
pcmpgtb xmm2, xmmword ptr Xmm_SL
pcmpgtb xmm3, xmmword ptr Xmm_30
В результате все байты регистра ХММ2
содержавшие символы больше и равно символу '0'
установлены в значение -1
, а меньше в значение 0
. Все байты регистра ХММ3
содержавшие символы больше и равно символу '1'
установлены в значение -1
, а меньше в значение 0
.
Инвертируем регистр
ХММ0
и выполняем логическую операциюAND
над регистрамиХММ0
иХММ2
результат которой помещаем в регистрХММ0
.
pandn xmm0, xmm2
В результате все байты регистра ХММ0
содержащие символы в диапазоне от '0'
до '9'
включительно, то есть цифры, принимают значения -1
а все остальные 0
.
Инвертируем регистр
ХММ1
и выполняем логическую операциюAND
над регистрамиХММ1
иХММ3
результат которой помещаем в регистрХММ1
.
pandn xmm1, xmm3
В результате все байты регистра ХММ1
содержащие символы в диапазоне от '1'
до '9'
включительно, то есть значащие цифры, принимают значения -1
а все остальные 0
.
Копируем старшие биты байтов регистра
ХММ0
вHASH_STR
pmovmskb HASH_STR, xmm0
В результате младшие 16 бит регистра HASH_STR
соответствуют 16 старшим байтам Числовой строки, при этом биты соответствующие символам содержащим цифры принимают значения 1
а все остальные 0
.
Копируем старшие биты байтов регистра
ХММ1
в регистрN_Z_CHAR
pmovmskb N_Z_CHAR, xmm1
В результате младшие 16 бит регистра N_Z_CHAR
соответствуют 16 старшим байтам Числовой строки, при этом биты соответствующие символам содержащим значащие числа, принимают значения 1
а все остальные 0
.
Повторяем операции описанные выше для младшей части Числа
movdqu xmm0,[CUR_CHAR]
movdqa xmm2, xmm0
movdqa xmm3, xmm0
pcmpgtb xmm0, xmmword ptr Xmm_39
movdqa xmm1, xmm0
pcmpgtb xmm2, xmmword ptr Xmm_SL
pandn xmm0, xmm2
pcmpgtb xmm3, xmmword ptr Xmm_30
pandn xmm1, xmm3
Копируем старшие биты байтов регистра
ХММ0
вEAX
.Сдвигаем младшие 16 бит
HASH_STR
в старшую частьHASH_STR
.Складываем
HASH_STR
иEAX
pmovmskb eax, xmm0
shl HASH_STR, xmmword
add HASH_STR, eax
В результате в HASH_STR
содержит хеш Числовой строки в котором биты соответствующие символам цифр установлены в значение 1
а в се остальные в 0
, при этом номера битов соответствуют номерам символов от начала строки начиная с нуля.
Копируем старшие биты байтов регистра
ХММ0
вEAX
.Сдвигаем младшие 16 бит
N_Z_CHAR
в старшую частьN_Z_CHAR
.Складываем
N_Z_CHAR
иEAX
.
pmovmskb eax, xmm1
shl N_Z_CHAR, xmmword
add N_Z_CHAR, eax
; #endregion
В результате в N_Z_CHAR
содержит хеш Числовой строки в котором биты символов соответствующие значащих цифр установлены в значение 1
а в се остальные в 0
, при этом номер бита соответствуют номерам символов от начала строки начиная с нуля.
Копируем
HASH_STR
вFRS_CHAR
.Сканируем
FRS_CHAR
от младшего бита к старшему в поисках первого бита равного1
, помещая результат в этот же регистр и устанавливаем флаг нуляZF=1
если все биты равны нулю.Если флаг нуля
ZF=1
то значит строка не содержит ни одного символа цифры и необходимо выйти из функции вернув код ошибки.Сбрасываем флаг нуля
ZF=0
если полученный результат отличен от нуля.Если флаг нуля
ZF=0
то значит первый символ строки не является цифрой и необходимо выйти из функции вернув код ошибки.
; проверка первого символа #region
mov FRS_CHAR, HASH_STR
bsf FRS_CHAR, FRS_CHAR
jz ErrorExit
test FRS_CHAR, FRS_CHAR
jnz ErrorExit ; первый символ не цифра
; #endregion
В результат проверяем содержит ли Числовой строки хотя бы один символ цифры и является ли первый символ Числовой строки цифрой. Особенностью данного участка кода в нестандартном поведении инструкции BSF
которая проявляется в работе с флагом нуля, а именно если при сканирование первым битом равным 1
окажется бит с порядковым номером 0
то BSF
установит значение регистра назначения в 0
но при этом сбросить флаг нуля ZF=0
как будто в регистре содержится число отличное от нуля, если же инструкция не обнаружит ни одного бита в состоянии 1
, то регистр назначение не будет подвергнут изменению а флаг нуля будет установлен в ZF=1
.
Инвертируем значение
HASH_STR
в результате чего теперь каждый бит установленный в1
сигнализирует о символе НЕ цифре.Копируем значение
HASH_STR
вDOT_CHAR
.Сканируем
DOT_CHAR
от младшего бита к старшему, помещая результат в этот же регистр и устанавливаем флаг нуляZF=1
если все биты равны нулю.Если флаг нуля
ZF=1
то значит строка не содержит ни одного символа отличного от цифры и необходимо выйти из функции вернув код ошибки.Сравниваем символ отличный от цифры с символом
'.'
и устанавливаем флагZF=1
если они не равны.Если флаг нуля
ZF=0
то значит первый символ отличный от цифры не равен символу'.'
и необходимо выйти из функции вернув код ошибки.
; поиск точки разделителя целой и дробной части Числа #region
not HASH_STR
mov DOT_CHAR, HASH_STR
bsf DOT_CHAR, DOT_CHAR
jz ErrorExit ; точки не обнаружено
cmp byte ptr[CUR_CHAR + DOT_CHAR], '.'
jnz ErrorExit ; символ не является точкой
; #endregion
В результате в DOT_CHAR
находиться указатель на символ '.'
относительно начала Числовой строки.
Копируем
N_Z_CHAR
вHASH_STR
используяHASH_STR
для временного хранения значенияN_Z_CHAR
.Сканируем
N_Z_CHAR
от младшего бита к старшему помещая результат в этот же регистр.Сохраняем в память строку из четырех нулей
'0000'
по адресу на1
(один) байт меньше адреса указанного вBUFF_STR
.Сохраняем в регистр
ХММ0
старшую часть строку символов начинающийся с первого символа значащей цифры, на который указываетN_Z_CHAR
, игнорирую таким образом ведущие нули.Сохраняем в память старшую часть строки символов по адресу указанному в
BUFF_STR
.Сохраняем в регистр
ХММ0
младшую часть строки символов на которую указываетN_Z_CHAR
со смещение в 16 байт.Сохраняем в память младшую часть строки символов начиная с первого символа значащей цифры по адресу указанному в
BUFF_STR
со смещение в 16 байт.
; сохранение значащий части Числа #region
mov HASH_EXP, N_Z_CHAR
bsf N_Z_CHAR, N_Z_CHAR
mov dword ptr[BUFF_STR - byte], 30303030h
movdqu xmm0,[CUR_CHAR + N_Z_CHAR]
movdqu [BUFF_STR + 00000000], xmm0
movdqu xmm0,[CUR_CHAR + N_Z_CHAR + xmmword]
movdqu [BUFF_STR + 00000000 + xmmword], xmm0
; #endregion
В результате сохраняем в память строку из 32 символов начиная с первого символа значащей цифры на которую указывает N_Z_CHAR
по адресу указанному в BUFF_STR
. При этом указанная строка может содержать точку и иные символы не относящиеся к цифрам.
Загружаем строку длиной 32 символа, следующую сразу после точки, на которую указывает
DOT_CHAR
в регистрыХММ0
иХММ1
.
; загрузка дробной части Числа #region
movdqu xmm0,[CUR_CHAR + DOT_CHAR + byte]
movdqu xmm1,[CUR_CHAR + DOT_CHAR + byte + xmmword]
; #endregion
Сбрасываем в
HASH_STR
бит указанный вDOT_CHAR
удаляя его из хеша, теперь при следующем сканировании бит указывающий на точку будет проигнорирован.Копируем
HASH_STR
вEXP_CHAR
.Сканируем
EXP_CHAR
от младшего бита к старшему помещая результат в этот же регистр устанавливая флаг нуляZF=1
если все биты равны нулю.Если флаг нуля
ZF=1
то значит строка не имеет корректного окончания и необходимо выйти из функции вернув код ошибки.
; поиск конца дробной части Числа #region
btr HASH_STR, DOT_CHAR
mov EXP_CHAR, HASH_STR
bsf EXP_CHAR, EXP_CHAR
jz ErrorExit
; #endregion
В результате в EXP_CHAR
находиться указатель на первый символ экспоненты или окончание Числа относительно начала Числа.
Сравниваем
EXP_CHAR
иN_Z_CHAR
и устанавливаем флаг переполненияCF=1
еслиN_Z_CHAR
большеEXP_CHAR
Копируем
EXP_CHAR
вN_Z_CHAR
еслиCF=1
; количество значащих символов Числа #region
cmp EXP_CHAR, N_Z_CHAR
cmovc N_Z_CHAR, EXP_CHAR
В результате если и целая и дробная часть Числа состоят из одних нулей а первый символ значащей цифры находиться за пределами числа , о чем свидетельствует факт того что N_Z_CHAR
больше EXP_CHAR
, то присваиваем N_Z_CHAR
значение EXP_CHAR
то есть указателя на первый символ экспоненты или окончания числа.
Сравниваем
N_Z_CHAR
иDOT_CHAR
и еслиN_Z_CHAR
меньшеDOT_CHAR
, то есть первая значащая цифра расположен раньше точки, что означает что у числа существует целая часть, устанавливаем флаг переносаCF=1.
Копируем в
LEN_NUMB
указатель на первый символ экспоненты или окончания Числа содержащийся вEXP_CHAR.
Вычитаем из
LEN_NUMB
указатель на первую значащую цифру содержащуюся вN_Z_CHAR
и флаг переносаCF.
cmp N_Z_CHAR, DOT_CHAR
mov LEN_NUMB, EXP_CHAR
sbb LEN_NUMB, N_Z_CHAR
; #endregion
В результате в LEN_NUMB
содержится значение количества цифр Числа начиная с первой значащей цифры без учета символа точки, то есть исключительно количество символов соответствующих цифрам, символ точки в подсчете не учитывается даже если число пересекает точку.
Вычитаем из
DOT_CHAR
значениеN_Z_CHAR
и устанавливаем флаг знакаSF=0
, если полученное число положительное.Помещаем в
OFF_CHAR
число19
равное количеству символов которое будет в дальнейшем использованы для создания мантиссы.Копируем
DOT_CHAR
вOFF_CHAR
еслиSF=0
Сохраняем в память старшую часть строки следующей сразу за символом "точки" со смещением указанным в
OFF_CHAR
по адресу указанному вBUFF_STR
Сохраняем в памяти младшую часть строки смешенную на 16 байт от символа "точки" со смещением указанным в
OFF_CHAR
, плюс 16 байт, по адресу указанному вBUFF_STR
; сохранение дробной части Числа #region
sub DOT_CHAR, N_Z_CHAR
mov OFF_CHAR, xmmword + dword - byte
cmovns OFF_CHAR, DOT_CHAR
movdqu xmmword ptr[BUFF_STR + OFF_CHAR + 0000000], xmm0
movdqu xmmword ptr[BUFF_STR + OFF_CHAR + xmmword], xmm1
mov N_Z_CHAR, HASH_EXP
; #endregion
В результате если число имеет целую часть то в OFF_CHAR
помещается длина целой части, в противном случае в OFF_CHAR
помещается длина Числа по умолчанию равная 19 байтам. Таким образом в случае наличия целой части, дробная часть будет записана в память сразу начиная с позиции символа "точки", то есть с "затиранием" символа "точки", в противном случае дробная часть будет записана за пределами строки подлежащей дальнейшему анализу и таким образом проигнорирована. Таким образом если число содержит целую и дробную часть они будут склеены в единую строку с удалением символа "точки".
Загружаем в ХММ2 строку символов
'0'
.Сохраняем в память строку символов
'0'
длиной 32 байта со смещением указанным вLEN_NUMB
по адресу указанному вBUFF_STR
; зануление недостающих символов Числа #region
movdqu xmm2, xmmword ptr Xmm_30
movdqu xmmword ptr[BUFF_STR + LEN_NUMB + 0000000], xmm2
movdqu xmmword ptr[BUFF_STR + LEN_NUMB + xmmword], xmm2
mov LEN_CELL, DOT_CHAR
; #endregion
В результат все "мусорные" символы числовой строки, находящиеся после последнего символа цифры, на который указывает LEN_NUMB
будут "затерты" символами "нуля". Таким образом в памяти будет сформирована строка начинающаяся с первого значащего символа, содержащая все значимые цифры и дополненная нуля в случае если значимая часть Числа меньше 19 символов.
Копируем в
ХММ0
строку символов начиная с первого символа экспоненты или окончания числа.Загружаем в регистр
HASH_EXP
бинарное значение0101h
.Копируем значение
HASH_EXP
вХММ1
одновременно расширяя его доXMMWORD
нулями.Переставляем байты регистра
ХММ0
в соответствии с номерами указанными вХММ1
. Таким образом первые два байта соответствуют второму символу а все оставшиеся первому символу на который указываетEXP_CHAR
.Сравниваем
ХММ0
со строкой символов в памяти содержащей 9 (девять) вариантов окончания строки 2 (два) варианта символа экспоненты и 2 (два) варианта знака экспоненты.Копируем старшие биты байтов
ХММ0
вHASH_EXP
.
; сканирование экспоненты #region
movdqu xmm0,[CUR_CHAR + EXP_CHAR]
mov HASH_EXP, 01010101h
movd xmm1, HASH_EXP
pshufb xmm0, xmm1
pcmpeqb xmm0, xmmword ptr Mask_001
pmovmskb HASH_EXP, xmm0
; #endregion
В результате в HASH_EXP
находиться хеш результата 13 сравнений первого и второго байта на который указывает HASH_EXP
.
Устанавливаем флаг нуля
ZF=0
если ни один из результатов сравнения на корректное окончание числа не дал результата.Чтото делаем, что именно спроси у командира
; !!!!! проверка окончания Числа #region
test HASH_EXP, 03FF0h
; место для паники!
; #endregion
В результате если результат любого сравнения на факт корректного окончания дал результата включаем режим паники, в противном случае продолжаем анализ Числовой строки.
Устанавливаем