On Sunday, September 24, 2023 at 8:27:50 PM UTC-5, Ben Bacarisse wrote:

> For example, the DJB hash of the string "abcdef" is 4048079738, but your
> code gives 1900599327. Your hash can go no higher than 2**31 - 2, but
> the original one uses the full range of 32-bit unsigned int.
>
> [...]
>
> This is why halving the range by using only 31 bits is not a good idea.
> It's not a /terrible/ idea because 31 bits is still a huge range, but
> since 32-bit wrapping is free on most hardware, there is absolutely no
> upside to using modulo 2147483647 arithmetic for a hash.
>
> And your saying "32bit - 1 as is the case" means you still don't know
> what the code you wrote is really doing.

Reader's from the future, re-read the 1st paragraph...

Here's where good ol' Ben has (unwittingly, chuckle) proven, & in his own
words mind you, the importance of using of using a unique key number.

On Friday, September 22, 2023 at 2:50:10 PM UTC-5, Michael Sanders wrote:

> Greetings folks, just sharing the knowledge (& test posting using google groups).

For the sake of completeness, a key generator (you supply a 32bit key):

# Michael Sanders 2023: key generator for dbj2() & dbj2gawk()
# # creates a key block (25 keys, 5x5 matrix) as shown below:
# # 2147483647 2147483646 2147483645 2147483644 2147483643
# 2147483642 2147483641 2147483640 2147483639 2147483638
# 2147483637 2147483636 2147483635 2147483634 2147483633
# 2147483632 2147483631 2147483630 2147483629 2147483628
# 2147483627 2147483626 2147483625 2147483624 2147483623

BEGIN {

KEYMAX = 2147483647 # your key's max number
BLOCKS = 5 # number of blocks to create

for (x = KEYMAX; x >= 0; x--) {
printf("%010d ", x);
if ((KEYMAX - x) % 5 == 4) {
printf("\n");
if (++y % 5 == 0) {
printf("\n")
if (--BLOCKS < 1) exit
}
}
}

}

Michael Sanders <chrome.tty@gmail.com> writes:

> On Sunday, September 24, 2023 at 8:27:50 PM UTC-5, Ben Bacarisse wrote:
>
>> For example, the DJB hash of the string "abcdef" is 4048079738, but your
>> code gives 1900599327. Your hash can go no higher than 2**31 - 2, but
>> the original one uses the full range of 32-bit unsigned int.
>>
>> [...]
>>
>> This is why halving the range by using only 31 bits is not a good idea.
>> It's not a /terrible/ idea because 31 bits is still a huge range, but
>> since 32-bit wrapping is free on most hardware, there is absolutely no
>> upside to using modulo 2147483647 arithmetic for a hash.
>>
>> And your saying "32bit - 1 as is the case" means you still don't know
>> what the code you wrote is really doing.
>
> Reader's from the future, re-read the 1st paragraph...
>
> Here's where good ol' Ben has (unwittingly, chuckle) proven, & in his own
> words mind you, the importance of using of using a unique key number.

What's a key number?

--
Ben.

On Monday, September 25, 2023 at 5:50:45 PM UTC-5, Ben Bacarisse wrote:

> What's a key number?

It doesn't matter Ben. I do appreciate your
willingness to help despite our p*ssing contest.
Moving forward, here's an intended usage example.

Given a CSV file of: Smith, John, HASH

And parsed as, oh something like:

if ($1 == "Smith" && $2 == "John") {

if ($3 == dbj2("policy_number")) {...}
}

We've gained simple a way to obfuscate small chucks
of patient records.

Michael Sanders <chrome.tty@gmail.com> writes:

> On Monday, September 25, 2023 at 5:50:45 PM UTC-5, Ben Bacarisse wrote:
>
>> What's a key number?
>
> It doesn't matter Ben.

OK. I thought you might want to be understood.

--
Ben.

Well, about to bring this little project to its conclusion =)
A special thanks (in no particular order) to:

Janis Papanagnou, Manuel Collado, & Ben Bacarisse.

Great insights, advice & help, appreciate you all.

tags: awk, sh, djb2, hash, keys, crypto

# Michael Sanders 2023: djb2 - simple string hash for awk
# # https://porkchop.neocities.org/notes/djb2.txt
# # usage example...
# # given a CSV file of: Smith, John, HASH
# # you could deploy djb2() in the following manner:
# # if ($1 == "Smith" && $2 == "John" && $3 == djb2("medical_condition")) {...}
# # if a unique number is desired, use one of the key generators below

function djb2(str, hash, x, y, ascii) {

hash = 5381
y = length(str)

for(x = 1; x <= y; x++) {
ascii = substr(str, x, 1)
hash = (hash * 33 + alphanum(ascii)) % ((2^32) - 1) # 32-bit key or
# hash = (hash * 33 + alphanum(ascii)) % 2147483647 # generated key
}

return hash

}

function alphanum(tmp) {

return index("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", tmp)

}

BEGIN {

print djb2("sensitive data")

}

# -----------------------------------------------------------------

# Michael Sanders 2023: key generator for djb2.awk
# # creates 1250 random & unique keys, where each block
# contains 25 keys within a 5x5 matrix, sample output:
# # 4044119583 2096446957 0146530746 2307162583 1145196028
# 2074570158 0782926302 0126577871 1957612719 1264962473
# 2768662034 3770197738 1165669763 3328823363 1160752685
# 1609089706 2699782284 0621370497 3966710650 2024400675
# 1453519246 1174954443 1588003602 3567230071 2877329117

BEGIN {

MIN = 0123456789 # min 10 digit num
MAX = 4294967295 # max 10 digit num
BLX = 50 # number of blocks

seed = systime(); srand(seed)
printf("\nSeed: %s\n\n", seed)

for (x = 1; x <= BLX; x++) {
for (y = 1; y <= 5; y++) {
s = ""
for (z = 1; z <= 5; z++) {
do {key = int(rand() * (MAX - MIN + 1)) + MIN} while(key in keys)
keys[key]
s = (s == "" ? sprintf("%010d", key) : s " " sprintf("%010d", key))
}
printf("%s\n", s)
}
if (x < BLX) printf("%s", "\n")
}
}

# -----------------------------------------------------------------

# Michael Sanders 2023: key generator2 for older awks using dbj2.awk
# # use this key generator instead if your awk lacks the abilty to
# use either large integers or the systime() builtin
# # creates key blocks (25 keys, 5x5 matrix) as shown below:
# # 2147483647 2147483646 2147483645 2147483644 2147483643
# 2147483642 2147483641 2147483640 2147483639 2147483638
# 2147483637 2147483636 2147483635 2147483634 2147483633
# 2147483632 2147483631 2147483630 2147483629 2147483628
# 2147483627 2147483626 2147483625 2147483624 2147483623

BEGIN {

KEYMAX = 2147483647 # your 10 digit max number
BLOCKS = 50 # number of blocks to create

for (x = KEYMAX; x >= 0; x--) {
printf("%010d ", x);
if ((KEYMAX - x) % 5 == 4) {
printf("\n");
if (++y % 5 == 0) {
printf("\n")
if (--BLOCKS < 1) exit
}
}
}

}

# -----------------------------------------------------------------

notes:

https://stackoverflow.com/questions/1579721/why-are-5381-and-33-so-important-in-the-djb2-algorithm

https://stackoverflow.com/questions/10696223/reason-for-the-number-5381-in-the-djb-hash-function

https://groups.google.com/g/comp.lang.c/c/lSKWXiuNOAk

https://en.wikipedia.org/wiki/Daniel_J._Bernstein

https://groups.google.com/g/comp.lang.awk/c/FZNpn8Sxf9k

# eof

--
:wq
Mike Sanders

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> OK. I thought you might want to be understood.

Well, I wake up in a new world everyday it seems =)

Have look up thread somewhere or another (subject
contains '[Complete]'.

--
:wq
Mike Sanders

porkchop@invalid.foo (Mike Sanders) writes:
[...]
> function djb2(str, hash, x, y, ascii) {
>
> hash = 5381
> y = length(str)
>
> for(x = 1; x <= y; x++) {
> ascii = substr(str, x, 1)
> hash = (hash * 33 + alphanum(ascii)) % ((2^32) - 1) # 32-bit key or
> # hash = (hash * 33 + alphanum(ascii)) % 2147483647 # generated key
> }
>
> return hash
>
> }
>
> function alphanum(tmp) {
>
> return index("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789", tmp)
>
> }
[...]

Why do you call this "djb2"?

Here's a description of the djb2 hash function from
<https://www.eecs.yorku.ca/~oz/hash.html>:

this algorithm (k=33) was first reported by dan bernstein many years
ago in comp.lang.c. another version of this algorithm (now favored
by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the
magic of number 33 (why it works better than many other constants,
prime or not) has never been adequately explained.

unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;

while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;
}

I see some similarities between the original djb and your hash function,
and yours was undoubtedly inspired by djb2, but they're very much not the
same thing. Would you agree that calling it "djb2" is misleading?

I find it odd that your function treats all non-alphanumeric characters
as the same. Is there a reason for that?

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

> Why do you call this "djb2"?

Well, because that is what its called.

> Here's a description of the djb2 hash function from
> <https://www.eecs.yorku.ca/~oz/hash.html>:

Yes, one of the links in the notes section has a reference to that url.
Did you not read the notes?

> this algorithm (k=33) was first reported by dan bernstein many years
> ago in comp.lang.c. another version of this algorithm (now favored
> by bernstein) uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the
> magic of number 33 (why it works better than many other constants,
> prime or not) has never been adequately explained.

I know, intesting stuff I thought!
> unsigned long
> hash(unsigned char *str)
> {
> unsigned long hash = 5381;
> int c;
>
> while (c = *str++)
> hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
>
> return hash;
> }

Here's my take in virtually indentical take in c (uint32_t):

uint32_t djb2(const char *str) {

uint32_t hash = 5381;
int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;
}
> I see some similarities between the original djb and your hash function,
> and yours was undoubtedly inspired by djb2, but they're very much not the
> same thing. Would you agree that calling it "djb2" is misleading?

Nope, wont change it either. =) I've provided my notes, so others can study it,
use it, extend it, trace it back to its source if so compelled... I make
no claims as to being its originator. Heck the *cough* notes *cough* alone
demonstrate that. I feel its 'nifty' for no reason than its short & sweet.
awk (or least I) needed this functionality. Besides, I'm hard-pressed to think
anyone will mistake it as anything misleading. I reckon no good deed will
go unpunished. Such is life on usenet...

> I find it odd that your function treats all non-alphanumeric characters
> as the same. Is there a reason for that?

Yes, just dealing (a-z, A-Z, 0-9) here. Personally don't want to imbue
it with extra, uneeded baggage. Feel free to modify it to suit your tastes.

--
:wq
Mike Sanders

porkchop@invalid.foo (Mike Sanders) writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> Why do you call this "djb2"?
>
> Well, because that is what its called.

You mean that's what you decided to call it. I'm asking why.

>> Here's a description of the djb2 hash function from
>> <https://www.eecs.yorku.ca/~oz/hash.html>:
>
> Yes, one of the links in the notes section has a reference to that url.
> Did you not read the notes?

I did. That's how I noticed that you've implemented a different
algorithm than any version of the original djb2.

[...]

>> I see some similarities between the original djb and your hash function,
>> and yours was undoubtedly inspired by djb2, but they're very much not the
>> same thing. Would you agree that calling it "djb2" is misleading?
>
> Nope, wont change it either. =)
[...]

Noted.

What you've posted is not djb2. You shouldn't claim that it is. You've
made it clear that you intend to continue to do so.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

> You mean that's what you decided to call it. I'm asking why.

Well, I don't think I have an anwser that will satisfy you.
> What you've posted is not djb2. You shouldn't claim that it is. You've
> made it clear that you intend to continue to do so.

What do you feel I ought to do to clarify the problem with this cavet:

It wont be taken down or renamed.

Perhaps add clarification to the document how my take only deals with
alphanumeric chars? Let's work it out.

--
:wq
Mike Sanders

porkchop@invalid.foo (Mike Sanders) writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> You mean that's what you decided to call it. I'm asking why.
>
> Well, I don't think I have an anwser that will satisfy you.

Then post an answer that doesn't satisfy me. So far you've said nothing.

>> What you've posted is not djb2. You shouldn't claim that it is. You've
>> made it clear that you intend to continue to do so.
>
> What do you feel I ought to do to clarify the problem

Rename it.

> with this cavet:
> It wont be taken down or renamed.

If you wrote a hash function that yields a 160-bit result that differs
from the result returned by the actual sha1 function, would you release
it under the name "sha1"? Assuming your answer is no, how is this
different? (Admittedly djb2 isn't as well established.)

> Perhaps add clarification to the document how my take only deals with
> alphanumeric chars? Let's work it out.

Work it out yourself.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

> Work it out yourself.

Will do.

--
:wq
Mike Sanders

Mike Sanders <porkchop@invalid.foo> wrote:

> Will do.

https://porkchop.neocities.org/notes/mHash.txt

--
:wq
Mike Sanders

On 26.09.2023 23:31, Keith Thompson wrote:
> porkchop@invalid.foo (Mike Sanders) writes:
> [...]
>
> Why do you call this "djb2"?
>
> Here's a description of the djb2 hash function from
> <https://www.eecs.yorku.ca/~oz/hash.html>:
> [...]
>
> I see some similarities between the original djb and your hash function,
> and yours was undoubtedly inspired by djb2, but they're very much not the
> same thing. Would you agree that calling it "djb2" is misleading?
>
> I find it odd that your function treats all non-alphanumeric characters
> as the same. Is there a reason for that?
>

Indeed. I as well was misleaded by the impression I've got that he
was trying to implement (just in a wrong way) an existing algorithm.
I noticed that (my) mistake not before I saw two versions of his code
in one post, each using different character set encodings - which of
course would lead to different results even if we compare only the
OP's own implementations' results. This arbitrariness in conjunction
with the inherent flaws the code versions had (and may still have;
I don't bother any more) makes clear that we obviously have a "Not
Invented Here" case (https://en.wikipedia.org/wiki/Not_invented_here),
which most likely makes all in depth discussions void anyway. Glad
it became obvious after all. (Bad that I noticed that too late. And I
see that the OP just recently followed your suggestion to rename his
hash function.)

It's always good to get information about the _intention_ of a piece
of posted code early and with the original post; that way bandworm
threads and misunderstandings could be avoided.

<OT>
Let's come back to the actual application and application domain ...

Inferred from the OP's posting where he wrote: dbj2("policy_number"))
and "simple a way to obfuscate small chucks of patient records." ...

In statistical medicine context there's demand to anonymize patient
data. For statistical purposes and cause-effect insights it's usually
necessary to be able to assign data to an "individual entity" without
disclosing his identity. But a hash code does not support that; it
can lead to "ID"-clashes that assigns different results to one same
subject. You need to create (real) keys. - Remember Ben's confusion
about (the OP's misnomer) "key number"! The OP may seem to require
keys but he's creating a hash value.

Of course if a hash value is sufficient - only the OP knows this! -
then I'd have used some existing and proven algorithm instead of
inventing my own (with possible flaws or non-obvious bad properties).
(But this as well has the OP to decide and is not an Awk question
anyway.)
</OT>

Janis

Wow... I've simply attempted to learn & share that with others.
I cant recall every seeing such, I dunno, at a loss for words.
It would've taken me a few more iterations to bring it all togther
but with this environment, its not okay.

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

> Indeed. I as well was misleaded by the impression I've got that he
> was trying to implement (just in a wrong way) an existing algorithm.
> I noticed that (my) mistake not before I saw two versions of his code
> in one post, each using different character set encodings - which of
> course would lead to different results even if we compare only the
> OP's own implementations' results. This arbitrariness in conjunction
> with the inherent flaws the code versions had (and may still have;
> I don't bother any more) makes clear that we obviously have a "Not
> Invented Here" case (https://en.wikipedia.org/wiki/Not_invented_here),
> which most likely makes all in depth discussions void anyway. Glad
> it became obvious after all. (Bad that I noticed that too late. And I
> see that the OP just recently followed your suggestion to rename his
> hash function.)
>
> It's always good to get information about the _intention_ of a piece
> of posted code early and with the original post; that way bandworm
> threads and misunderstandings could be avoided.
>
> <OT>
> Let's come back to the actual application and application domain ...
>
> Inferred from the OP's posting where he wrote: dbj2("policy_number"))
> and "simple a way to obfuscate small chucks of patient records." ...
>
> In statistical medicine context there's demand to anonymize patient
> data. For statistical purposes and cause-effect insights it's usually
> necessary to be able to assign data to an "individual entity" without
> disclosing his identity. But a hash code does not support that; it
> can lead to "ID"-clashes that assigns different results to one same
> subject. You need to create (real) keys. - Remember Ben's confusion
> about (the OP's misnomer) "key number"! The OP may seem to require
> keys but he's creating a hash value.
>
> Of course if a hash value is sufficient - only the OP knows this! -
> then I'd have used some existing and proven algorithm instead of
> inventing my own (with possible flaws or non-obvious bad properties).
> (But this as well has the OP to decide and is not an Awk question
> anyway.)
> </OT>
>
> Janis
>

--
:wq
Mike Sanders

On Wednesday, September 27, 2023 at 3:04:03 AM UTC-5, Janis Papanagnou wrote:

> Of course if a hash value is sufficient - only the OP knows this!

key = 32bitmax - random_lesser

(admin issues keys so no duplicates)