Why is high nibble like that?

[Ygg01]

Reading SIMD Json paper pg 8 I note the high nibble is [8, 0, 17, 2, 0, 4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0] while the high nibble value is

simdjson/src/arm64.cpp

Line 51 in bf78341

const simd8<uint8_t> table2(8, 0, 18, 4, 0, 1, 0, 1, 0, 0, 0, 3, 2, 1, 0, 0);

I was able to reverse engineer this, somewhat...

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	high nibble
0										8	8			8			8
1
2	16												2				18
3											4						4
4
5												1		1			1
6
7												1		1			1
8
9
A
B												1?	2?	1?			3
C													2?				2
D												1?		1?			1
E
F
low nibble	16									8	12	1	2	9			x

My question is where does 3, 2, 1 come from? I ask because I have different set of characters to check, and not sure how to adapt it.

Is this used for UTF8 tests?

[lemire]

@Ygg01 Section 3.1.2 (which covers about 2 pages) describes in details vectorized classification.

Have you read all of the text (about a full page)? Do not start from the figure. It is the wrong way to figure it out. You must read the text first.

You may also enjoy these posts:

• "Recognizing string prefixes with SIMD instructions," in Daniel Lemire's blog, July 14, 2023.
• "Decoding base16 sequences quickly," in Daniel Lemire's blog, July 27, 2023.
• "Locating ‘identifiers’ quickly (ARM NEON edition)," in Daniel Lemire's blog, September 4, 2023.

[Ygg01]

@Ygg01 Section 3.1.2 (which covers about 2 pages) describes in details vectorized classification.

First off thanks for that lovely document. I read it and watched the presentation - pure 10/10 stuff.
However, that's what I'm asking about. In vectorized classification, there is the following excerpt:

See Table 1. The table for the low nibbles is 16, 0, 0, 0, 0, 0, 0, 0, 0, 8, 10, 4, 1, 12, 0, 0; and the table
for the high nibbles is 8, 0, 17, 2, 0, 4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0.

(Section 3.1.2 pg 7->8)

Emphasis mine. When I compare it to code from simd-json.rs or simdjson it's not what I expect to see.

-8, 0, 17, 2, 0, 4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0 // from document
+8, 0, 18, 4, 0, 1, 0, 1, 0, 0, 0, 3, 2, 1, 0, 0 // from code

Doing some backwards calculation, I can compute that desired values for classifier were shifted a bit.

code point	paper desired values	code desired values
0x2C	1	2
0x3A	2	4
0x5B, 0x5D, 0x7B, 0x7D	4	1
0x09, 0x0A, 0x0D	8	8
0x20	16	16

However, that doesn't explain B, C, D high nibbles. These nibbles aren't even in ASCII. I assume the discrepancy is a step I'm missing.

To simplify my questions:

1. Why are high nibbles for B, C, D are 3, 2, 1 respectively? What am I missing here?
2. Does changing bits from the paper to production code have some sort of performance impact?

[lemire]

I can compute that desired values for classifier were shifted a bit.

The paper is from 2019. It describes simdjson as it stood on June 12 2019. We are about five years later, so it no longer matches the paper. You should be able to go back in time with git. E.g., clone the project and then do git checkout 871fd20ee54a0da43888521586630a916df4318a or any commit of your choosing.

However, the paper was not designed to be read with the code. You are expected to understand the algorithm from the paper alone.

Maybe if you explain what part of the paper you do not understand, we might be able to help you.

[Ygg01]

However, the paper was not designed to be read with the code. You are expected to understand the algorithm from the paper alone.
Maybe if you explain what part of the paper you do not understand, we might be able to help you.

Think there is a misunderstanding. My problem's with the code, not the paper. Both paper high nibble and my own high nibbles agree.

Alright. Let me show my work. I tried to find them independently for my own code. For these classifier values:

code point	code desired values
0x2C	2
0x3A	4
0x5B, 0x5D, 0x7B, 0x7D	1
0x09, 0x0A, 0x0D	8
0x20	16

I constructed the following low/high nibble table. I OR all columns to get low nibble values and OR all rows to get high nibbles.

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	high nibble
0										8	8			8			8
1
2	16												2				18
3											4						4
4
5												1		1			1
6
7												1		1			1
8
9
A
B
C
D
E
F
low nibble	16									8	12	1	2	9			x

Based on that, I get the following values low nibbles (16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 1, 2, 9, 0, 0) and high nibbles (8, 0, 18, 4, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0).

Verification step: I will see what simdjson uses.

simdjson/src/arm64.cpp

Lines 50 to 51 in bf78341

	const simd8<uint8_t> table1(16, 0, 0, 0, 0, 0, 0, 0, 0, 8, 12, 1, 2, 9, 0, 0);
	const simd8<uint8_t> table2(8, 0, 18, 4, 0, 1, 0, 1, 0, 0, 0, 3, 2, 1, 0, 0);

The low nibbles are correct, but high nibbles value differ. Why? Additionally, the nibbles differ on bytes 0xB_, 0xC_ and 0xD_ ( where _ is standing for unknown low nibble). These bytes that are out of ASCII range and shouldn't be in the classifier.

Question: What is causing the difference? Am I missing a step? Or is this an error in high nibbles?