Comparing with C would involve setting up a working C compilation
environment, I'm too lazy for that... :P
Spent some time finding bit op combinations for mask creation, amongst
others, a mask which, when AND'ed with the input byte, can be OR'ed into a
compound header byte.
AND that with 2r00111110 at the end, and voila, you know if the string is
valid Latin1 :)
The mask in question:
createMultiByteHeaderMaskOf: utfByte in: maskReg using: asm
"Create a mask in maskReg where all bits are 1 for multibyte headers, and
zero for others"
"Invalid patterns:
10XXXXXX - Non-header byte of multibyte character
0XXXXXXX - Single byte character
Valid:
110XXXXX - Two-byte character header
1110XXXX - Three-byte character header
11110XXX - Four-byte character header"
asm "Invalid
Valid Invalid"
mov: maskReg with: utfByte; "10XXXXXX 11XXXXXX
0XXXXXXX"
shr: maskReg with: 1; "010XXXXX 01100000
00XXXXXX"
and: maskReg with: utfByte; "000XXXXX 01XXXXXX
00XXXXXX"
shl: maskReg with: 1; "00000000 10000000
0XXXXXX0"
sar: maskReg with: 7. "00000000 11111111
00000000"
In the end, I now have a fallback path for codepoint counting/String class
determination which should be easy (barring alignment, and SEGV guards) to
vectorize with MMX/SSE/AVX paths :D
(For that I guess I'd also need to find the image where I put that nice
CPUID class I made long ago, and figure out a jumpless method of doing the
actual decoding as well...
Oh, and I still have to implement UTF8 encoding, plus at least UTF16 and a
callback to use Image-decoders if something more esoteric is desired, I
guess those take priority)
There's already quite a few methods involved, I guess in the end, these
will be put in NBXXXConverter(s), which, in addition to the emit: methods
that can be used from NB methods (like ExternalString marshalling), will
respond to an encodeString:/decodeBytes: interface.
Cheers,
Henry
p.s.
The naughtiest one yet, which, (if it's bug-free), is used to find what
value to increase the source reg by when counting characters:
createAdvanceOf: utfByte in: advanceReg using: gen
"Create an advance in advanceReg, telling us how many characters we can
skip"
"Input:
10XXXXXX - Non-header byte of multibyte character - advance 1 (should
never end up reading this in a valid utf string)
0XXXXXXX - Single byte character - advance 1
110XXXXX - Two-byte character header - advance 2
1110XXXX - Three-byte character header - advance 3
11110XXX - Four-byte character header - advance 4
"
"Code with no jumps.
This method would not be of any use in vectorized code, since that
scans a set stride length at a time, and can't exploit highbyte/lowbyte
movs anyways.
Why then? Because bsr is cooler than a bunch of jmps:, that's all.
This is the last op in loop, so we don't care if utfByte happens to
gets clobbered by the bsr"
"make sure advanceReg is the high byte of a register, so bsr will count
correctly"
advanceReg isHighByte ifFalse:[self error: 'Current assembly only
accepts a highbyte to hold advance!'].
"If only we'd stored this somewhere during character counting..."
self createMultiByteHeaderMaskOf: utfByte in: advanceReg using: gen asm;
gen asm
and: advanceReg with: utfByte; "110XXXXX
1110XXXX 11110XXX 00000000"
shl: advanceReg with: 1; "10XXXXX0
110XXXX0 1110XXX0 00000000"
xor: advanceReg with: 16rFF; "01XXXXX1
001XXXX1 0001XXX1 11111111"
bsr: advanceReg as16 with: advanceReg as16; "00000111
00000110 00000101 00001000"
shl: advanceReg as16 with: 8; "Put the bit
scan results back in actual advanceReg"
sub: advanceReg with: 9; "11111110
11111101 11111100 11111111"
xor: advanceReg with:16rFF; "00000001
00000010 00000011 00000000"
inc: advanceReg. "00000010
00000011 00000100 00000001"
On Fri, Jun 27, 2014 at 7:58 PM, Igor Stasenko <siguctua(a)gmail.com> wrote:
> Don't compare with smalltalk, compare with C! :)
>
>
> On 27 June 2014 19:23, phil(a)highoctane.be <phil(a)highoctane.be> wrote:
>
>> Impressive numbers and a nice examplz to grasp lots of NB/Asm details.
>> Le 27 juin 2014 18:55, "Henrik Johansen" <henrik.s.johansen(a)veloxit.no>
>> a écrit :
>>
>> >
>> > Soo, I started dabbling with the thing I talked about before last
>> summer, letting String parameters in NB calls have an encoding: option.
>> > (Thereâs already a slice in inbox to allow optional values other than
>> true/false)
>> >
>> > Thought Iâd start with decoding; hereâs a small preview of the part
>> which does the actual decoding, after needed string class has has been
>> determined and instantiated.
>> > While itâs a fallback path for when the platform doesnât support SSE or
>> other batch operations, itâs still using some neat tricks (imho) I thought
>> others might enjoy on a Friday afternoon :)
>> >
>> > emitStandardDecodeUTF8CharactersFrom: aSource to: aDestination
>> withCharSize: aCharSize scratchReg: scratchReg using: aGenerator
>> > "Emit decoding using only standard x86 ops"
>> > "We have already found what String class is needed for decoding
>> aSource, and created an instance of the proper size"
>> > "This implementation focuses on minimizing jumps and register
>> usage, at the cost of loading from source one byte at a time.
>> > "Input:
>> > aSource - memory pointer to C-string with UTF8 bytes
>> > aDestination - memoryPointer to first var field of
>> String instance
>> > scratchReg - a register which will be modified while
>> decoding
>> >
>> > aCharSize - The size in bytes of each character in our
>> destination string, known at emission time
>> >
>> > Clobbers: scratchReg
>> > aSource and aDestination will end up pointing to end of strings"
>> >
>> > | asm scratch32 sLowByte sHighByte loop done oneByte twoBytes
>> threeBytes |
>> >
>> > asm := aGenerator asm.
>> > loop := asm uniqueLabelName: 'utf8DecodeLoop'.
>> > done := asm uniqueLabelName: 'utf8DecodingDone'.
>> > scratch32 := scratchReg as32.
>> > sLowByte := scratch32 as8.
>> > sHighByte := sLowByte asHighByte.
>> >
>> > asm label: loop.
>> > "Unroll the inner loop as many times as we want, or, well, at
>> least as many times as the backwards jump will allow us to"
>> > 8 timesRepeat:[
>> > oneByte := asm uniqueLabelName: 'utf8OneByteDecode'.
>> > twoBytes := asm uniqueLabelName: 'utf8TwoByteDecode'.
>> > threeBytes := asm uniqueLabelName: 'utf8ThreeByteDecode'.
>> > asm xor: scratch32 with:scratch32.
>> > asm or: sLowByte with: aSource ptr8.
>> > asm cmp: sLowByte with: 0.
>> > asm je: done.
>> > asm add: aSource with: 1.
>> > asm test: sLowByte with: 2r10000000 asUImm8.
>> > asm jz: oneByte.
>> > "We have a header, place its data bits as initial high byte
>> value"
>> > asm shl: scratch32 with: 8.
>> > asm xor: sHighByte with: 2r11000000 asUImm8. "Strip 2 byte
>> header"
>> > asm test: sHighByte with: 2r00100000.
>> > asm jz: twoBytes.
>> > aCharSize > 1 ifTrue: [
>> > asm xor: sHighByte with: 2r00100000. "Strip 3 byte header"
>> > asm test: sHighByte with: 2r000100000.
>> > asm jz: threeBytes.
>> > "This is a 4-byte character"
>> > asm xor: sHighByte with:2r00010000."Strip 4 byte header"
>> > "Read one trailing byte, remove the header, and shift the data
>> out of low byte"
>> > asm or: sLowByte with: aSource ptr8.
>> > asm shl: sLowByte with:2.
>> > asm shl: scratch32 with: 6.
>> > asm add: aSource with: 1.
>> > asm label: threeBytes.
>> > "Read one trailing byte, remove the header, and shift the data
>> out of low byte"
>> > asm or: sLowByte with: aSource ptr8.
>> > asm shl: sLowByte with:2.
>> > asm shl: scratch32 with: 6.
>> > asm add: aSource with: 1.
>> > ].
>> > asm label: twoBytes.
>> > "Read last trailing byte, remove header, and shift the data
>> bits into proper place"
>> > asm or: sLowByte with: aSource ptr8.
>> > asm shl: sLowByte with:2.
>> > asm shr: scratch32 with: 2.
>> > asm add: aSource with: 1.
>> > asm label: oneByte.
>> > asm mov: (aDestination ptr size: aCharSize) with: (scratch32
>> as: aCharSize).
>> > asm add: aDestination with: aCharSize.].
>> > asm jmp: loop.
>> > asm label: done.
>> >
>> > And the relevant test code for that:
>> >
>> > testStandardDecodeWide
>> > | bytes string |
>> > "bytes := (ZnUTF8Encoder new encodeString: 'Cash, like â¬, is
>> king'), #[0]."
>> > bytes := #[67 97 115 104 44 32 108 105 107 101 32 226 130 172
>> 44 32 105 115 32 107 105 110 103 0].
>> > string := WideString new: bytes size - 1.
>> > self testStandardDecode: bytes toWideString: string.
>> > ^ string
>> >
>> > testStandardDecode: utf8Bytes toWideString:aString
>> > <primitive: #primitiveNativeCall module: #NativeBoostPlugin>
>> > ^ self nbCallout
>> > function: #(void #(char* utf8Bytes, char* aString ))
>> > emit: [ :gen :proxy :asm |
>> > asm pop: asm EBX;
>> > pop: asm ECX.
>> > self emitStandardDecodeUTF8CharactersFrom: asm
>> EBX to: asm ECX withCharSize: 4 scratchReg: asm EAX using: gen.
>> > asm mov: EAX with: gen proxy nilObject ]
>> >
>> > Which, though itâs currently cheating by pre-knowledn string
>> class/size, isnât alot of overhead:
>> > ext := NBExternalString new.
>> > [ext testStandardDecodeWide] bench '5,030,000 per second.' '5,080,000
>> per second.' '5,190,000 per second.â
>> > Compared to an equivalent to testStandardDecodeWide, with emitStandardâ¦
>> removed from the primitive:
>> > [ext testEmptyDecode] bench '5,850,000 per second.' '5,800,000 per
>> second.' '5,640,000 per second.'
>> >
>> > ⦠or compared to doing the decoding in image after the call:
>> > int := ZnUTF8Encoder new.
>> > [int decodeBytes:#[67 97 115 104 44 32 108 105 107 101 32 226 130 172
>> 44 32 105 115 32 107 105 110 103 0]] bench '130,000 per second.' '131,000
>> per second.' '132,000 per second.â
>> >
>> > Cheers,
>> > Henry
>> >
>>
>>
>
>
> --
> Best regards,
> Igor Stasenko.
>
