Replacing single byte in doubleword

Robert AH Prins

unread,

Apr 18, 2012, 11:29:19 AM4/18/12

to

Is there a smart non-SIMD way of replacing a single byte in a
doubleword, let's say a comma by a space or an asterisk by a zero, other
than a loop, like

mov ecx, 4

@1:
cmp al, "," ; or whatever
jne @2

mov al, " " ; or whatever

@2:
rol eax, 8
dec ecx
jnz @1

given that the character to be replaced occurs only once (or not at
all), and that it never occurs on the first iteration of the loop,
something the above code doesn't even take into account.

Robert
--
Robert AH Prins
robert(a)prino(d)org

Jim Leonard

unread,

Apr 18, 2012, 10:03:33 AM4/18/12

to

On Apr 18, 10:29 am, Robert AH Prins <spamt...@prino.org> wrote:
> Is there a smart non-SIMD way of replacing a single byte in a
> doubleword, let's say a comma by a space or an asterisk by a zero, other
> than a loop, like

I'm not sure if it's smart, but a 128K lookup table would allow
something like "replace, ROL EAX,16, replace". No branches, but you
burn 128K for the table.

Terje Mathisen

unread,

Apr 18, 2012, 12:48:18 PM4/18/12

to

64K or 128K lookup tables are less bad than you'd guess, simply because
the inputs are normally regular text, from a quite limited character
set. This means that the working set will be significantly less than 128
K, so it might fit in L1 cache.

The generic non-SIMD way to handle bytes in parallel would require you
to use one of the zero-byte detection codes, use that to generate 00/FF
masks for the matching bytes and then ADD/SUB/XOR in the offset between
the old and the new value.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

pe...@nospam.demon.co.uk

unread,

Apr 19, 2012, 1:53:02 AM4/19/12

to

In article <jr7369-...@ntp6.tmsw.no>

Assuming comma to space, maybe something like this?

; value in EAX

xor eax, 02c2c2c2ch ; ",,,,"
mov ebx, 02c2c2c0ch ; remask... 2C -> 20
test eax, 0000000ffh
jz replace
test eax, 00000ff00h
mov ebx, 02c2c0c2ch
jz replace
test eax, 000ff0000h
mov ebx, 02c0c2c2ch
jz replace
test eax, 0ff000000h
mov ebx, 00c2c2c2ch
jz replace
mov ebx, 02c2c2c2ch ; restore original

replace: xor eax, ebx

I've no idea how much faster this might be than your shift/loop but
it's certainly smaller than 64K ;-)

Pete
--
Believe those who are seeking the truth.
Doubt those who find it. - André Gide

hopcode

unread,

Apr 19, 2012, 2:40:21 AM4/19/12

to

Il 18.04.2012 18:48, Terje Mathisen ha scritto:
>
> 64K or 128K lookup tables are less bad than you'd guess, simply because
> the inputs are normally regular text, from a quite limited character
> set. This means that the working set will be significantly less than 128
> K, so it might fit in L1 cache.
>

64K or 128K lookup tables !?
a possible NO-LUT solution for ANSI SIMD/NOSIMD:

http://sites.google.com/site/x64lab/home/my-own-fanciful-snippets-1/finding-a-byte-in-a-dword-qword

Cheers,

--
.:mrk[hopcode]
.:x64lab:.
group http://groups.google.com/group/x64lab
site http://sites.google.com/site/x64lab

Terje Mathisen

unread,

Apr 19, 2012, 5:29:06 AM4/19/12

to

Ouch!

No,no: You want this code to be branchless!

If you know that the inputs are 7-bit ascii you can do it like this:

mov ebx,eax
xor eax,2C2C2C2Ch ; Turns comma into zero byte
sub eax,01010101h ; 80h or higher for zero input
and eax,080808080h ; 80h mask for each byte to be converted
shr eax,5 ; 04h --------- " ------------------
lea eax,[eax+eax*2] ; 0Ch mask, difference between ',' and ' '
sub ebx,eax ; Output in EBX

Robert AH Prins

unread,

Apr 19, 2012, 7:43:30 AM4/19/12

to

Not yet tested, but given that it has four jumps which aren't very
predictable, it might actually take longer.

Robert AH Prins

unread,

Apr 19, 2012, 7:47:48 AM4/19/12

to

On 2012-04-19 06:40, hopcode wrote:
> Il 18.04.2012 18:48, Terje Mathisen ha scritto:
>>
>> 64K or 128K lookup tables are less bad than you'd guess, simply because
>> the inputs are normally regular text, from a quite limited character
>> set. This means that the working set will be significantly less than 128
>> K, so it might fit in L1 cache.
>>
> 64K or 128K lookup tables !?
> a possible NO-LUT solution for ANSI SIMD/NOSIMD:
>
> http://sites.google.com/site/x64lab/home/my-own-fanciful-snippets-1/finding-a-byte-in-a-dword-qword

I actually looked at Paul Hsieh's page
<http://www.azillionmonkeys.com/qed/asmexample.html> for the code to
uppercase ASCII (example 11), but somehow I couldn't figure out how to
make it do what I needed.

hopcode

unread,

Apr 19, 2012, 6:46:22 AM4/19/12

to

one possible solution using a replace mask.
it should be the fastest, but i cannot test it now for all 8 bits.

.replace:
mov ecx,20202020h ;--- char to find 20h
mov ebx,30303030h ;--- replace found chars with 30h
mov eax,[string] ;--- example 31322034h
mov edx,eax
and eax,ecx
xor eax,ebx
and eax,edx
xor edx,ecx
xor eax,ebx
add eax,edx ;--- resulting string
ret 0

Robert AH Prins

unread,

Apr 19, 2012, 10:23:44 AM4/19/12

to

That was what I was trying to do using Paul Hsieh's code as skeleton,
but couldn't figure out - I was trying to convert the x'80' into an XOR
mask to make the changes, but the SUB method is rather easier.

Thanks,

hopcode

unread,

Apr 19, 2012, 10:51:04 AM4/19/12

to

emmm.. sorry, :-) i was too late i couldnt test,
this one should work fine. the algo is parted in 2 stages:

mov ecx,20202020h ;--- find mask
mov eax,31322034h ;--- string

.f&r:
mov ebx,eax
xor eax,ecx
not eax
mov edx,eax
and eax,ecx
not ecx
and edx,ecx
add edx,01010101h
and eax,edx
xor eax,ebx
nop
mov ecx,eax
mov ebx,40404040h ;--- replace mask
not eax
mov edx,eax
and eax,ebx
not ebx
and edx,ebx
add edx,01010101h
and eax,edx
not ebx
or eax,ecx ;--- 31324034h
ret 0

pe...@nospam.demon.co.uk

unread,

Apr 19, 2012, 1:49:28 PM4/19/12

to

In article <3g2569-...@ntp6.tmsw.no>

"terje.mathisen at tmsw.no"@giganews.com "Terje Mathisen" writes:

> pe...@nospam.demon.co.uk wrote:
> > [rubbish code...]

>
> Ouch!
>
> No,no: You want this code to be branchless!
>
> If you know that the inputs are 7-bit ascii you can do it like this:
>
> mov ebx,eax
> xor eax,2C2C2C2Ch ; Turns comma into zero byte
> sub eax,01010101h ; 80h or higher for zero input
> and eax,080808080h ; 80h mask for each byte to be converted
> shr eax,5 ; 04h --------- " ------------------
> lea eax,[eax+eax*2] ; 0Ch mask, difference between ',' and ' '
> sub ebx,eax ; Output in EBX
>
> Terje

Nice :-) Took me a while to work that out -- converting FF to 0C!
I'll get my coat...

hopcode

unread,

Apr 21, 2012, 6:07:09 AM4/21/12

to

...and finally :-) parsing all 8 bits, for all type of masks.

i dont know a valid alternative (apart SSE) how to create a mask
of 0FFhs from the 80hs using bitwise & regs

i.e: from 80008080 -> to FF00FFFFh
any suggestion ?

Ok,my final proc

.find&repl:
mov eax,3138|20|35h ;<-- source string
mov ebx,eax

mov ecx,20202020h ;<--- find mask

xor eax,ecx
not eax
mov edx,7F7F7F7Fh
and edx,eax
xor eax,edx
add edx,01010101h
and eax,edx
nop

;--- create mask 0FF from 80
cdq
mov ecx,edx
ror eax,8
ror ecx,8
cwd
mov ch,dl
rol eax,8
rol ecx,8
cwd
mov ch,dl
cbw
mov cl,ah
nop

;--- replace --------------
mov eax,ecx
not ecx
and ebx,ecx
and eax,40404040h ;<--- replace mask
or eax,ebx ;<--- 3138|40|35h
ret

hopcode

unread,

Apr 21, 2012, 9:53:19 PM4/21/12

to

and found a little gem to convert from 80008080h -> to FF00FFFFh

;--- create mask 0FF from 80

mov ecx,eax ;<--- 80008080h
shr ecx,7 ;<--- 01000101h
add eax,eax ;<--- 00010100h
sub eax,ecx ;<--- FF00FFFFh

Il 21.04.2012 12:07, hopcode ha scritto:
> i dont know a valid alternative (apart SSE) how to create a mask
> of 0FFhs from the 80hs using bitwise & regs
> i.e: from 80008080 -> to FF00FFFFh

Cheers,