|
Just consider if your table size is a multiple of 5...
The hash value itself, even if it's a power of 2, is not sufficient: the multiplier msut be a coprime of the integer size (a power of 2, so the multiplier must not be even) cannot AND of ANY hash table size (which can be quite arbitrary integer, not necessarily a power of 2).
That's why using primes is always better. And why usually, the factor used in Fast Knuth Algorithm is a prime near the value of sqrt(2^(N-1)), for a generated hash value in [0, 2^N), i.e. the largest prime near below 2^(N/2); for a 32-bit hash value this means using the prime factor just below 65536, like 65521 or 65537 (but the 1st is better as the number of bits 1 or 0 are more equally balanced); but if your hash value will index strings of 1-byte characters or variable-length array of bytes (which are 4 times smaller in bitsize than the hash value), you'll use a factor near 2^4, rounded up to take into account for short strings, so you'll use the factor 17 (which contains 2 bits set to 1 and 2 bits set to 0: it is balanced and has good randomization properties): using a factor of 17 is also very fast to compute even if you don't have hardware multiplier in the instruction set of your ALU, or even if you don't have hardware shifts (it can be computed noly with 5 additions in that case, and a single pair of CPU registers; but this use is now extremely rare except in very cheap 8-bit controlers).
|
|
|
|
|
That's a strange argument given that this was about encryption, not a hash. It's supposed to be an invertible operation, that's all. There is no table.
|
|
|
|
|
A hash may be invertible if it contains at least as many bits as the input (though it is not is major usage where this is geenrally the reverse).
But the arguments are the same: you just want a perfectly flattened distribution of bits in the result, and for using it as an encryption, you must ensure that there will NEVER be any collision (so the distribution is almost perfectly flattened with collision lists for each hash value being either 1 or 0, a property that a good hash algorithm should have as well when their input has the same (or smaller) bitsize as their output. But actually a good hash will want to have this flattened distribution even if you truncate the hash value to less bits (the same will be true if you use it as an invertible encryption that must be secure, i.e. where you cannot guess the decryption key if you konw some pairs of clear-text input and resulting "hash" value, which should still be invertible but only when you know the decryption key or when you can generate it easily because you know the encryption key).
Many encryption algorothms also depend a the existence of a "securely strong" hash key (at least to generate the encryption/decryption keys), and the inversible operation of encrypting/decrypting may as well be used as a hashing function (once you give it one of the keys).
Note that encrypting very short messages even with a very strong encryption algorithm with long keys causes a major problem because the result is no longer a flat distribution; that's why strong encryptions require padding those messages with enough bits so that they become longer than the minimum length required for the keys. Such padding are not random, but they cannot be static (e.g. all zeroes), but should be generated by a strong hash: very short messages will then become undistibuishable from long messages that have the desired flattened distribution of bits in their encrypted patterns.
|
|
|
|
|
hash values are not random
|
|
|
|
|
I did not say they are "random", jsut that they are "sufficiently randomized" (meaning that it generates a sufficiently "flattened" distribution in the hash space to minimize the number of collisions of keys and the average access time in the hash table). Generally keys used in hash tables are not flattened, and that's where you need a good hashing function that *pseudo*-randomizes the distribution of their bits.
I've seen videos using STUPID hash functions like:
int hash(char*s) {
hash=0;
for (i=0, s[i] != '\0', i++) hash = hash*(i+1) + s[i];
return hash%N;
}
Here of course this is stupid as not all characters in the string have the same weight, some of them are even completely ignored in the result.
If you don't know what is a hash function and what it must respect, your hash table will not optimize anything and in fact lookups in such hash table will be even SLOWER than a full table-scan where you add keys at end of an array.
If you don't know which factor to use for computing hash value, just use 17, and use an hash table size which is a power of 2 (at 2^4, but an hash table size of 32, 64, 128 or 256 is better); if your hash table size is larger, adjust the factor so that it is rougly doubled (keeping it as a prime) when the hash table size is quadrupled (and take into account the bitsize of each individually "fragment" of the hash key that you "feed": most apps will feed basic integers or bytes). And for evaluating the table size needed, consider the number of keys you'll store, and IF collisions will be managed by storing keys in a separate linked link list, or in "successor" free slots inside the table itself (which increase the "fill factor" and the likelyhood of collisions with other hashes): your hash table should be about 33% to 67% filled with keys to avoid wasting space while keeping collisions still infrequent, with average length of collision lists per bucket lower than 1 (this will be true only if you've used a "good enough" hashing function that corerctly flattens the distribution of bits in the generated hash value space).
|
|
|
|
|
This not encryption or anything mysterious, it is simply copying unsigned char 8 bit into a 32 bit type by bit wise operations not all the time. NOT encryption.
|
|
|
|
|
The RA8875 is a controller for an 800x480 display I am using in a project.
You can rotate the screen via setting some registers.
There is no option to rotate 90 degrees, only 270, leaving the X axis, and thus text and bitmaps mirrored.
Whoever designed this should be forced to use it.
Real programmers use butterflies
|
|
|
|
|
Can't you just rotate it 3 times to get 90 degrees? Inelegant, but I must be missing something.
|
|
|
|
|
It's not quite 5am and my spatial reasoning may not be entirely on point right now.
Basically when I rotate it, it goes 90 degrees with the X axis inverted.
You cannot rotate it 3 times nor flip the X axis because they only use 2 bits to store the rotation.
These are the directions you can set the memory write order:
LRTD
RLTD
TDLR
DTLR
(T=Top, R=Right, D=Down, L=Left)
Real programmers use butterflies
|
|
|
|
|
I'm missing the TLDR option
|
|
|
|
|
Because you can mirror the x axis yourself reading the lines backwards.
GCS d--(d-) s-/++ a C++++ U+++ P- L+@ E-- W++ N+ o+ K- w+++ O? M-- V? PS+ PE- Y+ PGP t+ 5? X R+++ tv-- b+(+++) DI+++ D++ G e++ h--- r+++ y+++* Weapons extension: ma- k++ F+2 X
|
|
|
|
|
Yeah, no. Because then you can't send bitmap data using DMA, and you need to generate a lot more bus traffic. The device should have been designed correctly.
Real programmers use butterflies
|
|
|
|
|
"Rotate" doesn't exist -- there are only flips, on three axes.
Odd that they provide only two bits when you need three.
|
|
|
|
|
Call it what you want. You know what I was talking about so I did my part. Prescriptivism is annoying.
Real programmers use butterflies
|
|
|
|
|
Could you do the rotation and then use the horizontal and vertical scan direction registers to mirror the display (and get an extra 180 degrees of rotation)?
|
|
|
|
|
It doesn't have registers for mirroring aside from the two bits it uses, and I need three.
Real programmers use butterflies
|
|
|
|
|
Register 20H instead of 40H/45H? Or is that the wrong controller I am looking at? It might be something completely different or not do what you need.
I agree, it does need three bits to get all of the rotations/mirrors that are possible and they have a spare bit, so why didn't they just give all eight options?
|
|
|
|
|
Fueled By Decaff wrote: Register 20H instead of 40H/45H?
Nice catch! I guess my eyes are glazing over it after poring over it for a day while writing a driver for it.
I'll see if it works.
I don't know why they didn't use 3 bits. It's just weird.
Real programmers use butterflies
|
|
|
|
|
|
Usually these IoT display controllers allow you to rotate any direction due to the screen orientation being unknown in advance. In any case, thanks to FueledByDecaf I worked it out by adjusting both the write order and the scan direction both.
Real programmers use butterflies
|
|
|
|
|
|
In my defense this code was generated by a tool. It's still some of the weirdest code to do string ops in SQL I've seen. Part of it is due to the fact that it converts everything to UTF32 as it goes, even though in this routine it really doesn't need to.
DROP PROCEDURE [dbo].[SqlCompiledChecker_IsCommentBlockBlockEnd]
GO
CREATE PROCEDURE [dbo].[SqlCompiledChecker_IsCommentBlockBlockEnd] @value NVARCHAR(MAX), @index INT, @ch INT
AS
BEGIN
DECLARE @adv INT
DECLARE @matched INT
DECLARE @valueEnd INT = DATALENGTH(@value)/2+1
DECLARE @tch BIGINT
DECLARE @accept INT = -1
DECLARE @result INT = 0
WHILE @ch <> -1
BEGIN
SET @matched = 0
IF @ch = 42
BEGIN
SET @index = @index + 1
SET @adv = 1
IF @index < @valueEnd
BEGIN
SET @ch = UNICODE(SUBSTRING(@value, @index, 1))
SET @tch = @ch - 0xd800
IF @tch < 0 SET @tch = @tch + 2147483648
IF @tch < 2048
BEGIN
SET @ch = @ch * 1024
SET @index = @index + 1
SET @adv = 2
IF @index >= @valueEnd RETURN -1
SET @ch = @ch + UNICODE(SUBSTRING(@value, @index, 1)) - 0x35fdc00
END
END
ELSE
BEGIN
SET @ch = -1
END
SET @matched = 1
GOTO q1
END
GOTO next
q1:
IF @ch = 47
BEGIN
SET @index = @index + 1
SET @adv = 1
IF @index < @valueEnd
BEGIN
SET @ch = UNICODE(SUBSTRING(@value, @index, 1))
SET @tch = @ch - 0xd800
IF @tch < 0 SET @tch = @tch + 2147483648
IF @tch < 2048
BEGIN
SET @ch = @ch * 1024
SET @index = @index + 1
SET @adv = 2
IF @index >= @valueEnd RETURN -1
SET @ch = @ch + UNICODE(SUBSTRING(@value, @index, 1)) - 0x35fdc00
END
END
ELSE
BEGIN
SET @ch = -1
END
SET @matched = 1
GOTO q2
END
GOTO next
q2:
RETURN CASE @ch WHEN -1 THEN 1 ELSE 0 END
next:
IF @matched = 0
BEGIN
SET @index = @index + 1
SET @adv = 1
IF @index < @valueEnd
BEGIN
SET @ch = UNICODE(SUBSTRING(@value, @index, 1))
SET @tch = @ch - 0xd800
IF @tch < 0 SET @tch = @tch + 2147483648
IF @tch < 2048
BEGIN
SET @ch = @ch * 1024
SET @index = @index + 1
SET @adv = 2
IF @index >= @valueEnd RETURN -1
SET @ch = @ch + UNICODE(SUBSTRING(@value, @index, 1)) - 0x35fdc00
END
END
ELSE
BEGIN
SET @ch = -1
END
END
END
RETURN 0
END
GO
DROP PROCEDURE [dbo].[SqlCompiledChecker_IsCommentBlock]
GO
CREATE PROCEDURE [dbo].[SqlCompiledChecker_IsCommentBlock] @value NVARCHAR(MAX)
AS
BEGIN
DECLARE @adv INT
DECLARE @ch BIGINT
DECLARE @tch BIGINT
DECLARE @index INT = 0
DECLARE @valueEnd INT = DATALENGTH(@value)/2+1
DECLARE @result INT
SET @index = @index + 1
SET @adv = 1
IF @index < @valueEnd
BEGIN
SET @ch = UNICODE(SUBSTRING(@value, @index, 1))
SET @tch = @ch - 0xd800
IF @tch < 0 SET @tch = @tch + 2147483648
IF @tch < 2048
BEGIN
SET @ch = @ch * 1024
SET @index = @index + 1
SET @adv = 2
IF @index >= @valueEnd RETURN -1
SET @ch = @ch + UNICODE(SUBSTRING(@value, @index, 1)) - 0x35fdc00
END
END
ELSE
BEGIN
SET @ch = -1
END
WHILE @ch <> -1
BEGIN
IF @ch = 47
BEGIN
SET @index = @index + 1
SET @adv = 1
IF @index < @valueEnd
BEGIN
SET @ch = UNICODE(SUBSTRING(@value, @index, 1))
SET @tch = @ch - 0xd800
IF @tch < 0 SET @tch = @tch + 2147483648
IF @tch < 2048
BEGIN
SET @ch = @ch * 1024
SET @index = @index + 1
SET @adv = 2
IF @index >= @valueEnd RETURN -1
SET @ch = @ch + UNICODE(SUBSTRING(@value, @index, 1)) - 0x35fdc00
END
END
ELSE
BEGIN
SET @ch = -1
END
GOTO q1
END
RETURN 0
q1:
IF @ch = 42
BEGIN
SET @index = @index + 1
SET @adv = 1
IF @index < @valueEnd
BEGIN
SET @ch = UNICODE(SUBSTRING(@value, @index, 1))
SET @tch = @ch - 0xd800
IF @tch < 0 SET @tch = @tch + 2147483648
IF @tch < 2048
BEGIN
SET @ch = @ch * 1024
SET @index = @index + 1
SET @adv = 2
IF @index >= @valueEnd RETURN -1
SET @ch = @ch + UNICODE(SUBSTRING(@value, @index, 1)) - 0x35fdc00
END
END
ELSE
BEGIN
SET @ch = -1
END
GOTO q2
END
RETURN 0
q2:
EXEC @result = SqlCompiledChecker_IsCommentBlockBlockEnd @value, @index, @ch
RETURN @result
END
RETURN 0
END
GO
Real programmers use butterflies
|
|
|
|
|
UTF16 ain't good enough for you?
|
|
|
|
|
UTF16 surrogate pairs exist, so no. Frankly, I wish UTF16 didn't exist at all. It seems a waste of everyone's time. No wonder MS adopted it.
Real programmers use butterflies
|
|
|
|
|
code salad.
CI/CD = Continuous Impediment/Continuous Despair
|
|
|
|
|