Problem: There is an input array of uint8_t values, and these need to be packed into a new array of uint32_t values. Groups of 4 input 8 bit bytes get packed into a single 32 bit integer (according to some user-defined formula).
What is a declarative mathematical formula for packing 4 x 8 bit integers into a 32 bit integer over a range of ints?
Let's say we have a function "f" that accepts an index and returns a 32 bit integer:
f(x) => in[x + 0] & (in[x + 1] << 8) & (in[x + 2] << 16) & (in[x + 3] << 24)
Here "x" is an 8 bit integer index into "in[]", so it must increment in steps of 4:
for (uint32_t x = 0; x < nr_bytes; x += 4) {
uint32_t res = f(x);
}
So f(x) is a function that maps out a space of values given an input that is incrementing by 4 each time. But what if we wanted a function that took the byte index as input instead, and didn't increment in batches of 4? This function could be called for any input index value, and "do the right thing". It would look like this:
f(x) => out[floor(x / 4)] |= (in[x] << ((x % 4) * 8));
Or something like that.. We could in theory create a bunch of threads and have each thread call this function. But the function has a side-effect - it doesn't return anything! How would we guarantee that each thread wouldn't try to "&=" into the same 32 bit integer in the "out" array as another thread? We can't. To do that we would somehow have to group "x" values for each thread so indexes that end up modifying the same 32 bit integer are processed in the same thread. The function would need some kind of "signature" (but not the return signature) that in this case would be "floor(x / 4)". A compiler could figure out that for all possible values of "x" the signature of the function returns values destined for "floor(x / 4)" of memory, and group threads accordingly.
From this and also work with vector graphics in shaders I can almost see a pattern. Computer math is "different" from regular math. Or computer math is a subset of math that is discrete. Lot's of usage of floor, abs and mod. From here:
Discrete mathematics is the study of mathematical structures that can be
considered "discrete" (in a way analogous to discrete variables, having a
bijection with the set of natural numbers) rather than "continuous"
(analogously to continuous functions). Objects studied in discrete
mathematics include integers, graphs, and statements in logic.
Stupid example: you want to plot a sine wave. A sine wave is a continuous function, but this must be mapped to pixel locations which are discrete. Continous variation is "change without jump".
In the example about number packing above I was trying to make a distinction between a "traditional" approach to packing (write the process of how to pack) and a declaration of the "shape" of packing. So you would write the relationship between two discrete chunks of memory, and the code to transform between these two "shapes" of memory could be written automatically. Not because it would be easier, but because it would be safer.
In the same way that continuous functions can declare the relationship between two real number domains, I am trying to think if we can treat computer memory as a domain (of what? bits?) and declare relationships between two areas of memory.