Post by @hipsterelectron@circumstances.run

d@nny disc@

@hipsterelectron@circumstances.run 4 hr. ago

build tool is now blocked on file-based checksum and i am L O C K E D the fuck in

15 Replies

6 Boosts

This comment is unavailable — it may have been deleted or is not visible to you.

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

what i was going to say:

i have a "simple" answer which considers a file as an unstructured contiguous bit string of known size. but one reason my directory checksum is very useful is the ability to maintain a hash tree independently of the input data that attests to the integrity of every recursive component.
this especially means you can merge hash trees (e.g. composing directories to form a chroot) and diff tree states (e.g. to capture output from a process execution) without reference to any object database
in other words you can create an algebra of filesystem states which is far more than merely "reproducible", and can actually describe what changed and whether that was correct

and all that is even more true with the flattened representation described above where each inode vertex has its directed graph relationships described completely independent of its identity

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

what i was trying to do was to shit on the "sponge construction" used in sha-3. it's sof ucking funny
https://en.wikipedia.org/wiki/Sponge_function

The sponge function "absorbs" (in the sponge metaphor) all blocks of a padded input string as follows:
S is initialized to zero
for each r-bit block B of P (string)
R is replaced with R XOR B (using bitwise XOR)
S is replaced by f(S)

what is f(S)? well,

f produces a pseudorandom permutation of the 2^b states from S.

in other words, f is the actual fucking hash function

Sponge function

class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length that can be used to model or implement many cryptographic primitives

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

like very literally f is producing a permutation (i.e. an encryption) that is predicated only upon the bits of S instead of a separate key. that's the actual definition of a hash function

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

that's why it's so deceptive to say "a hash function produces a smaller output". no it doesn't!!!!

; printf '' | wc -c
0
; printf '' | sha256sum 
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 -

that's an encryption! and that sucks if i actually want to know what my data is, as opposed to wanting my data to be secret. using the same construct for cryptographic signatures is completely fucked when applying it to data integrity

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

and it's also just completely not the way hashes are used literally ANYWHERE else. the reason bloom filters work is because the hash functions are crafted to achieve collisions without having to calculate pairwise bit-for-bit equality over each pair of database entries!

radix sort gets better than n log n runtime for this exact reason!

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

so i refuse to call it a "hash". it's a "checksum" at best

d@nny disc@

@hipsterelectron@circumstances.run 3 hr. ago

i fervently believe that describing an actual literal parse forest for the file content that comes from actually parsing the data in an application-specific context is the correct way to achieve both data compression as well as integrity.

if the value of a single bit modifies the semantics of the entire rest of the file, that's information you kinda do need to know!

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

i actually refer to it as a "parse graph" to be fully general, because in fact most data serialization formats do not neatly compose into nested paired delimiters and a single "parse tree".

once you describe the relationships between atomic data blocks, you can directly use the parse graph to record checksum values that summarize not just the bits in your data, but what the bits mean.

and you (the application developer with domain expertise) can and should be able to construct a hash function that clearly summarizes the important facets of your data structure

d@nny disc@

@hipsterelectron@circumstances.run 2 hr. ago

"compression" is such a curious problem statement and it deserves some lambasting. see my diatribe on UTF-8 at https://codeberg.org/cosmicexplorer/corporeal.

the reason i prefer the term "coding theory" over "information theory" is that a "code" at least is designed to solve a problem.

the problems of "compression" and "integrity" are quite literally just variant encodings of the same set of assumptions.

Codeberg.org

corporeal

String library that uses corpus dictionaries to produce a more efficient encoding than UTF-8.

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

the reason i got way into this is because it ended up being a corollary of the parsing theory i developed in 2020-2022 because i was pissed off that parsing was so fucking annoying to do

one particular result that astounded me about the "algorithm" i developed (i hate that word) is that once my compiled parser processes any given sequence of tokens (e.g. "abca") in one input, the result of that work (the set of valid sub-parses spanning those tokens) can be directly reused for any later input.

i had never encountered an algorithm which amortized across problem instances before. like globally, across all possible inputs

(cc @somebody)

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

one reason the discussion of hashing kind of terrifies me is that the only other algorithm with this kind of property i'm aware of (where work performed for one input can be shared globally across others)..............

............is the one developed by lenstra using the sunzi remainder theorem to crack the discrete log problem

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

however, math always comes from somewhere. the reason my parser compiler was able to work like that is because i:

identified all possible "states" corresponding to individual tokens (i.e. if "a" is used in two places, it means two different things).
- upon beginning the parse, each token is replaced with the multiplicity of possible states.
identified all possible state transitions (not token transitions, but states) allowed by the user-specified grammar (my grammar language is like EBNF if EBNF just worked and did what you wanted it to do), and codified the transitions between each state using a metric fuckton of stack symbols.
- the stack symbols enable non-local inference by having a positive or negative valence. when you transitioned into case 2 of production A, you would add a positive gensymmed stack symbol, and a transition out of case 2 production A would induce a negative version of that symbol.
- this means that instead of backtracking and actually trying to specify individual paths depth-first, i essentially perform a breadth-first traversal of the entire possible state space corresponding to each token-state

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

to be clear, this was not terribly efficient. i was not looking to be efficient. i was looking to produce a grammar model that would be genuinely better than a switch-table recursive-descent parser.

masaru tomita's GLR parsing method in fact solves the same subproblem that i had to, and he did it much better. so i could steal an optimization from his phd thesis

d@nny disc@

@hipsterelectron@circumstances.run 1 hr. ago

there's a particular reason why it's possible to transfer work performed from one subproblem to another. it's because the input is assumed to arise from the same underlying distribution.

now of course this was achieved by construction with the problem statement i used for my parser compiler--i specifically assumed that all input matches my grammar, and i made "before-the-start" and "after-the-end" into synthetic "states" so that there was no distinction between an infinite stream of tokens and a finite-length message.

and finally, the work i performed was to rule out all interpretations that didn't match a specific token extent.

the point i'm making is that completely by chance, largely for aesthetic reasons, i ended up constructing a problem statement that achieved this incredibly weird global progress mechanism

d@nny disc@

@hipsterelectron@circumstances.run 59 min. ago

the thing about a parser compiler is that the user describes exactly the grammar they want to match. so they're actually constructing a representation of their desired data structure through the grammar interface--which then also happens to be serializable.

(and yes, you can run the grammar in reverse to generate "random" inputs, but this is actually much harder than it sounds for nontrivial grammars. however, serializing a concrete data structure is very straightforward)

Discussion

Discussion