A collection of notes and half-baked ideas and other things I wanted to write down to help clarify in my own mind or explain to somebody else.
I’m also quite bad at making a coherent point, so my hope is that by writing things down I’ll be able to iterate on them until they begin to make sense. One day. Maybe.
Posts
-
CISC-V: code compression in the style of a CISC architecture
Given a mixed-length instruction stream like Thumb or RVC you encounter a few different headaches. The most infamous case is the complexity of handling un-aligned 32-bit instructions which can straddle architectural boundaries like page or cache line boundaries. There are also caching and security implications of being able to jump into the middle of an instruction, and multi-issue problems with recognising correct instruction start points, and so on…
-
In-filling 3D prints with holes
I got to thinking about 3d printing infill the other day, and eventually I decided that there should be ways of scooping large chunks out of the middle, rather than in-filling with an homogenous sparse pattern, and retaining some or all of the original strength of the homogenous fill.
-
Choosing n different colours for graphs
One way to generate a palette of colours for distinguishing different lines and objects in diagrams is to take regular steps around the hue parameter of the HSL colour wheel. If you know how many you’ll need then your can subdivide the space evenly, or if you do not then you can use 1/φ as the interval instead. But this has limitations…
-
Designing a Lego card shuffler
A problem with mechanical card shufflers is that they do things like riffles with mechanical precision, and mechanical precision tends to produce predictable outcomes (at least in theory). Thinking about this gave me the idea that I could do my own but with deliberate and controlled use of robust random numbers in order to produce a true shuffle.
-
Getting even light from long LED strips
Something you may notice for very long runs of LED strip is that they can be bright at one end and dim at the other. That’s because the strips are two long power rails with a bit of internal resistance and current through the LEDs at the far end have more of that resistance to travel through.
-
Initialisation at declaration considered harmful
The trouble with always initialising variables at definition, and how it weakens tools which should be there to help you diagnose logic errors. -
An experimental RISCV instruction compression
I wanted to experiment with a means of reducing compiled RISCV code size in a way that did not allow for the creation of un-aligned 32-bit opcodes, so I had a bit of a tinker with 32-bit packets containing instruction pairs.
-
How I made a gzip encoder faster than memcpy
In the compression world it’s usual to compare the time spent compressing and decompressing data with the time difference in transmitting the compressed or uncompressed data over a given network. In this experiment I managed to make the compression faster than the bandwidth to RAM. Sort of. Under special circumstances and with no apologies for the egregious clickbait headline.
-
Hiding messages in machine-generated text
On a whim I thought I’d try getting ChatGPT to do a bit of steganography for me. There are a bazillion ways (give or take) for hiding a secret message in unrelated cleartext, where there’s a trade-off of secret bandwidth against cleartext flexibility. I chose Morse code encoded in the last letter of each word, because it’s obvious and easy to express as rules that anybody can follow.
-
Generating nonsense text even more efficiently
In my previous post, for the purpose of defining performance expectations I compared the way in which I was generating text (Mad-Libs style string substitution and concatenation) to Lempel-Ziv text decompression. That is, it’s simply the task of scheduling a series of string copies of various lengths and offsets. The complexity of deciding which strings to copy comes in one case from decoding the input stream to get the instructions, or in the other case from navigating tables and picking randomly from them.
-
Poisoning badly-behaved AI crawlers
Regardless of how you feel about generative AI stealing your job or filling creative spaces with slop or whatever, one thing I hope is less debatable is that their crawlers should still obey the rules of the road.
-
Pointer authentication weakness and mitigations
Pointer authentication involves taking things like the return address and inserting an authentication tag into unused bits – a cryptographic signature – before storing the pointer to memory, and then confirming that the signature agrees with the pointer destination after loading it back from memory and before using it again.
-
Entropy coding as a text generator
The compression gains of entropy coding revolves around making likely symbols short and unlikely symbols long. In principle you have some pre-arranged model of the string you want to compress and decompress, and you use that model to tell you the likelihoods that different symbols will turn up next and then you distribute the coding space accordingly, so it takes very few bits to land in the likeliest buckets and many more bits to force the outcome to land in an improbable bucket.
-
Automatic wiki
A project I’ve wanted to do for a long while now, ia a dynamically generated wiki. Use generative AI to produce an encyclopedic-looking page of text with a topic deduced from the URL and the random seed determined by a hash of the URL.
-
My tmux and zsh configuration
Here’s a list of things I have in my tmux and zsh configurations, which might offer some inspiration to others.
-
Extending range of numpy modular arithmetic
A frustration with numpy is that its
pow()implementation doesn’t support modular arithmetic. -
Using tags on Github Pages
Suppose you want to include a list of tags to the top of each post, and you want those tags to link to a page which lists all posts which include that tag. There are plugins but none available on GitHub Pages1, so here’s my workaround.
-
Maybe you can set up your own automation with more plugins available? ↩
-
-
Clipboard subversion on StackOverflow
Because Markdown is really a mixture of Markdown syntax and raw HTML to fill in gaps where Markdown can’t do the job, having user-generated content in Markdown format doesn’t help to curb malicious content. Users are still publishing HTML and have opportunities to embed something malicious or sneaky.
-
Non-binary Linear Feedback Shift Registers
There’s way too much documentation about binary LFSRs out there, and not a whole lot on doing the same with other bases. So I’ve put together some tables and a few notes so everybody can throw something together without to much effort.
-
Stupid font tricks
I thought I’d try creating an LFSR in font substitution tables to turn a string of the same character into a string of random variants of that character to make things appear more organic.
-
Spinach
Yesterday I was reminded of the occasion on which I first learned about spinach having not as much iron as commonly believed, and that the idea came down to a transcription error. I wasn’t really confident in my recollection so I went and looked it up and fell into reading about “Academic urban legends”.
-
Extended checks on manual arithmetic
So you’ve done some arithmetic by hand and now you want to make sure it’s correct. Casting out nines is the conventional sanity check, but that has weaknesses. What if you want something stronger? Try this one weird trick.
-
Invisible, universe-tweaking portals
I’m not going to describe the mechanics of the game [Portal][]. You probably already know; but I’ve often wittered on about how I think hidden portals would be a great way to tweak the universe and fold a map back on itself.
-
Trying to improve mipmap blending
LINEAR_MIPMAP_LINEAR, blending from one mipmap level to the next, is an interesting bodge. It approximates a dynamic cut-off frequency with linear interpolation between adjacent log2 cut-off frequencies. -
Light field aperture synthesis from drone flight path
For a low-rate-of-change scene like a construction site, I think it should be possible to use a drone with a camera on it to repeatedly fly through the same grid pattern in the sky, where that grid represents a large aperture, collecting compound images as if it were a light-field camera.
-
Hybridising zip files with an alternate compression scheme
An interesting feature of zip files (and consequently many formats which are just zip files renamed) is that all the identifying data appears at the end of the file with links back to content earlier in the file. This makes it possible to leave gaps in the middle or even at the beginning of the archive, which is why a self-extracting zip file can be decompressed on any architecture by using a native zip extractor.
-
Heatmap-based triangulation
About ten years ago a bunch of these little Bluetooth “key finder” gadgets hit the market (eg., Tile, TrackR, Chipolo, and eventually AirTag), and after thinking about how much use they’d be I began to wonder if it could be made easier to find them in a messy room, or long grass, or whatever, doing better than the RSSI-based numerical distance estimate that you could get on your phone.
-
stochastically ordering items by frequency
If you believe your histogram, when sorted, will fit a particular curve, then, like stochastic counters which conditionally increment based on a probability suitable to the conditions, you could perform stochastically filtered swaps to conditionally promote items up the list based on a probability. I guess the theory includes a flat probability but I don’t see the point in that.
-
Address-coded endian
Many years ago I found in an old Arm manual a description of the permutation that would happen to a 32-bit word loaded from an un-aligned offset. I don’t recall what the pattern was, but it looked like the barrel shifter had been repurposed to handle sub-word addressing of bytes and then masking deferred because it was a full-width read, even though the address was rounded down.
-
Naturally-aligned compressed opcode encoding
In the world of fixed-length instruction sets, the addition of compressed instructions (no-longer fixed-length instructions) is kind of a nuisance. Arm dropped them when they went to AArch64, and there was a proposal to make them optional in RISC-V but it didn’t fly.
-
Hinting train of branch directions in advance
Long ago I had to do a scaling operation which would yield a stream of branch decisions based on whether or not a row pointer would advance and need the subsequent row to be recalculated. I decided to try to calculate the branch decisions well in advance, and shift them into a shift register and then to branch on the least significant bit of that register and then do a right-shift to schedule the next branch decsion. I think the code is in AOSP somewhere.
-
Digging in to Pingback and Webmention
The other day I found out what a “Pingback” was, after I saw a bunch of them at the bottom of a widely-cited blog post. So I set about digging in to all that.
-
Font-based digit grouping
Struggling to read absurdly large numbers in terminal windows many years ago, I wondered how I might apply some logic in the terminal to subtly bunch together groups of three digits as a form of thousand separator. Eventually it occurred to me to try doing it in the font with ligature rules (initially as a joke, but then I looked into it) and it turned out Numderline was a thing which already did that.
-
Neighbourhood sampling order during texture filtering
In my pixel-art scaling tinkering I found a source of glitches in anti-aliased threshold operations involving derivative functions in shaders. So I worked out a workaround which saves me having to think too hard about a bunch of corner cases.
-
Scaling pixel art with SDF
For a while I’ve been wondering if giving a fantasy console like PICO-8 a graphics system defined in terms of more scalable low-memory primitives would lead to a more interesting retro style than the conventional sharp-edged squares. Not concepts like low-poly 3D or minified SVG (eg., RIPscrip), but maybe using pixel art scaling algorithms natively, or with additional markup in the data to clarify intent (sharpening corners, for example). Simply bake them into your pixel-art editor so you see what you’re going to get once it’s upscaled, with the option to correct it where it goes awry.
-
Embedded web content without all that JavaScript cruft
In an earlier blog post I wanted to embed some diagrams. Really I wanted SVG for clean scaling between devices, but I don’t have that format as an output option.
-
A pick-resistant lock design
There are a fair few attempts at “unpickable” locks out there, and overall I don’t think I have a great deal to add to the range of pre-existing methods. But a couple of years ago I thought I might have a go at my own design anyway.
-
Error resilience in rolling-intra
Rolling intra is where a portion of each coded video frame is encoded without reference to any previous frame, guaranteeing that that part of the scene can be reconstructed when joining or re-joining a stream without previous context.
-
Digits for a base-210 system
My own contribution to the field of making up improbable alien number systems involves counting in base 210. Rather than try to define 210 distinct symbols, or to make a 14-upon-15 or 15-upon-14 digit pair system, I chose to break each digit down into three components mod 5, mod 6, and mod 7.
-
Optimising Adler-32 checksum
The Adler-32 checksum consists of two 16-bit sums. One is the sum of all the bytes in the data, plus one, and the other is the sum of all those intermediate sums, which works out to be the same as the sum of all the bytes multiplied by their distance from the end of the buffer plus the length of the buffer. Both modulo 65521.
-
On the endianness of bitstreams
Where I’m from conventional wisdom has always been that while it’s an objective fact that little endian is the one-true-and-correct endian, bit-streams should always be packed as big-endian data.
-
Curl is not secure by default
I often find that when there’s been some debate about a topic on the internet the conclusion might be a thorough debunking of a bad idea but also a failure to address a more nuanced idea – or sometimes even a more fundamental idea.
-
What I've learned so far about CSS, SVG, Liquid, and Jekyll
From the point of view of knowing almost nothing about how any web techology works, here’s a bunch of stuff I had to pick up to draw a picture in a GitHub-powered blog.
-
A Latin-Square-based L1 cache layout
If I were going to build some kind of fantasy machine I would not fuss about making it high-performance. Mine would just be a mash-up of random things I found interesting at some point.
-
Bit-sliced matrix multiply
There’s a matrix multiplication in the middle of a lot of popular things, right now, and it’s in an operation which frequently tolerates remarkably low precision.
-
Pivot-sorting quick sort
Regarding those quick-sort variants which do things like median-of-k pivot selection before subdividing…
-
Hash map reduction operations
I notice that some defaults for things like STL
unordered_mapare a bit scary. The function to reduce the range of the hash down to the size of the table is remainder, and the default hash for integers is the identity function. -
A reasonably effective hash instruction
As per part one of this post, I have reasoned through and tested a proof of concept for generic CPU instruction which could achieve most of the required mixing of a good hash function in a single cycle (working with a combinational depth of 20 to 24 gates as a guide).
-
Why I want a dedicated hash instruction
A good hash function is expected to remove correlations of various sorts between subsets of inputs and their hashed outputs in order to mitigate the risk of those correlations producing performance aberrations (cache collisions, unbalanced structures, etc.) or statistical biases.
-
Idly musing over RowHammer mitigation strategies
Watching a RowHammer talk (slides) a while back (not actually the linked one, but I couldn’t find the one I attended) left me with a couple of thoughts about possible mitigations which I didn’t see discussed.
-
Machine innervation
Looking at the faults my espresso machine develops over time, I’ve often wondered if fault detection and error messages could be better. It’s probably safe to assume that the cost of including sensors for all possible faults and developing code to check and understand all those sensors is prohibitive and unreliable, so I’ve wondered about a different approach.
-
N-bit Mixer Functions
For reasons I intend (hah!) to go into in a longer post I was looking for operations with which to construct and whiten (or “finalise” or “mix” or “avalanche” or whatever) RNGs with 2n periods. I was looking at splitmix64 which led me to Fast splittable pseudorandom number generators which cited Improving on MurmurHash3’s 64-bit Finalizer (although I found that page by other means) and finally MurmurHash3 which tells me where those constants and that construction both come from.
-
Minimally biased NPOT-ranged random numbers
In my previous post I described a technique for scaling random numbers to new intervals producing extremely small bias but with a constant execution time.
-
Random number scaling
I’ve been doing some messing around with random number generation at work, and this inspired me to revisit something which has troubled me since my teenage years: Perfectly unbiased random numbers over a range which is not a power of two.
subscribe via RSS