This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). You could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. However, it would makeI'm not sure whether the program as a whole longercould be shortened like this, because a lot of it would have to be redone (e.g. the centre of the program would be inmove so you'd need to place the wrongoutput routine in a different place, and you'd need much morethat means moving the padding to push it over an Eelsewhere in order to do output properlythe program).
This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). You could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. However, it would make the program as a whole longer, because the centre of the program would be in the wrong place, and you'd need much more padding to push it over an E in order to do output properly.
This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). You could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. I'm not sure whether the program could be shortened like this, because a lot of it would have to be redone (e.g. the centre of the program would move so you'd need to place the output routine in a different place, and that means moving the padding elsewhere in the program).
In order to convert regular little-endian binary to Gray code, we basically need to output, for each bit, the XOR of that bit with the previous bit. The program has jumped to one of four locations based on whether the two bits we just read are 00, 01, 10, or 11; and each of these locations immediately calls an output subroutine to output 0, 1, 1, , or 10`, or 0 respectively.
This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). In the version of the program with comments removed, youYou could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. I'm not sure whether thatHowever, it would translate to byte savings inmake the restricted-source versionprogram as a whole longer, because the centre of the program, though would be in the wrong place, and it'd require redoing the whole programyou'd need much more padding to find out, so I'm happy with what I have at the momentpush it over an E in order to do output properly.
In order to convert regular little-endian binary to Gray code, we basically need to output, for each bit, the XOR of that bit with the previous bit. The program has jumped to one of four locations based on whether the two bits we just read are 00, 01, 10, or 11; and each of these locations immediately calls an output subroutine to output 0, 1, 1, or 0` respectively.
This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). In the version of the program with comments removed, you could save three bytes via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. I'm not sure whether that would translate to byte savings in the restricted-source version of the program, though, and it'd require redoing the whole program to find out, so I'm happy with what I have at the moment.
In order to convert regular little-endian binary to Gray code, we basically need to output, for each bit, the XOR of that bit with the previous bit. The program has jumped to one of four locations based on whether the two bits we just read are 00, 01, 10, or 11; and each of these locations immediately calls an output subroutine to output 0, 1, 1, or 0 respectively.
This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). You could save three bytes from this part of the code via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. However, it would make the program as a whole longer, because the centre of the program would be in the wrong place, and you'd need much more padding to push it over an E in order to do output properly.
Incident, 100 bytes
@``aaqscbjnNFNLllnjnnfdlLDDdeEDLHJJBBbfd`bcCK[SCGGEGFFB@@HIIKCAIMM]UQAEMmikKJHXxzz{{kcCAackjzZ[[{sqq
I/O is done by character (actually byte) code, because Incident is a horrible low-level tarpit with no numeric I/O routines. The program can handle numbers greater than 255 by using multiple characters (enter the number you want in little-endian base 256).
Explanation
In Incident, the tokens are not fixed by the language but rather defined by the program – any substring of the program that appears exactly 3 times is a token, unless it's contained within another token or overlaps another token. Additionally, the actual bytes that make up a token don't matter – just how the copies of the tokens are arranged relative to the other tokens.
In this program, I picked single-byte tokens to implement the program, choosing the bytes that represent them in order to get an approximate "only one bit changes from one byte to the next" property, and added extra bytes (that appear more or fewer than 3 times) as comments in order to make the property perfect. Thus, every occurrence of a byte in ]eimQSUxXZ fNs cCn is a comment, because it appears 1, 2, or 4 times respectively. (I had to double one of the ns to "detokenise" n; other padding characters added to maintain the one-bit-at-a-time property naturally ended up being used 1, 2 or 4 times.) The actual choice of bytes to represent the tokens, and positions of the padding bytes, was mostly done via a computer search (and the algorithm wasn't optimal, so this is probably golfable, but I haven't found anything better so far).
Removing the comments gives us the following 72-byte program, whose token arrangement was chosen by hand:
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
Incident programs are generally very hard to explain, so I'm going to attempt to explain this one by highlighting subsets of characters and explaining what they do. I think I've covered the whole program here, but in a program as unreadable as this one (and which was partially computer-generated, so I didn't entirely write it myself), it's quite possible that I've missed something.
Starting the program, and the first two bits of input
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
@ b HJJBBb b @@H k Hzz{{k k
Incident reads standard input a bit at a time (which is the only reason why writing this program is remotely viable in Incident – it's normally a horrible language for just about anything). If the three uses of a token are split as a lone token and a touching pair (e.g. @ … @@), that represents a jump from the single token to the double token, so the program starts by jumping from the @ at the start to @@.
To do input (the usual way, at least), the program must run into the middle of the three occurrences of a token, without ever hitting the first or last use. H here therefore reads the first bit (the least significant bit of the input number), and jumps to the first or last H accordingly.
In either case, we then cross over a couple of jump labels (JJBB or zz{{). For a backwards jump (which all of JBz{ are), it's safe to do this; control just moves past the jump label, like you'd expect for a jump label. (This is not safe for a forwards jump – you're encountering the middle of three uses without ever hitting the first or last, which is interpreted as an attempt to read input rather than an attempt to move past a jump label.)
This part of the program finishes by reading the second bit of input, using b or k based on whether the first bit read was a 0 or a 1 bit. Control flow is thus sent to one of four locations, based on the two most recent bits read.
Output subroutines
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
bj bK kK kj
j lljdl j
K IIKAI K
d DDdED d A MMAEM A
L L E L GGEG E
The outer uses (first and last) of any given token are basically subroutine calls, with the middle use being the entry and exit point from the subroutine (i.e. running the first or last token will jump to the middle, and then returning to the middle will return to just after the token you called it from).
We want to output 0 if we read two 0s or two 1s. We want to output 1 if we read 01 or 10. Output in Incident is done by calling a subroutine using the token that's the centremost token in the entire program (which for this program is E; the L token is dead code, with none of its uses ever reached, and it exists only to push the centre of the program over an E); its left call point outputs a 0 bit as a side effect, and its right call point outputs a 1 bit as a side effect. So we have a d subroutine that outputs 0 bits, and an A subroutine that outputs 1 bits, both via calling E. Because subroutines have their entry and exit points in the same place, we wrap each of them in a backwards jump to allow control flow to return to the point from which they were called.
Each Incident subroutine must be called from exactly 2 points in the program, but we have three locations that want to output 0 bits (and three locations that want to output 1 bits). The usual way to fix this is with helper/wrapper subroutines that contain nothing but a call to another subroutine, here j and K; j outputs 0 bits by calling d, and K outputs 1 bits by calling A. These wrapper subroutines use up one of the call points of the subroutine they're calling, but provide two (an increase of one call point), so this technique makes it possible to call d and A from three points each.
In order to convert regular little-endian binary to Gray code, we basically need to output, for each bit, the XOR of that bit with the previous bit. The program has jumped to one of four locations based on whether the two bits we just read are 00, 01, 10, or 11; and each of these locations immediately calls an output subroutine to output 0, 1, 1, or 0` respectively.
Moving from one bit to the next
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
jF BBb FFB
K[ {{k [[{
JJ b KJ
zz k jz
After we've produced our output, we need to move onto the next bit. The output of the binary-to-Gray conversion only ever depends on the most recent two bits, so we effectively just need to jump to the same location that the H which reads the first bit does – after producing output after a 0 bit, we need to jump to the b that handled input after a 0 bit is read, and after producing output after a 1 bit, we need to jump to the k that handled input after a 1 bit is read.
This is almost very straightforward, just using jumps to return to the relevant part of the program. After reading 10 or 11, we can do exactly that (using J and z respectively as the jump labels) – those are backward jumps, so control flow can safely pass over their jump labels. After reading 00 or 01, though, we would need to jump forward in the program rather than backward jumps, and control flow can't pass over a forward jump label safely. So instead, we need to jump forwards to an arbitrary point in the code, and then backwards to the point we actually need, allowing the two control flows to merge safely. This is done with F then B after reading 00, and [ then { after reading 01.
This handles most of the program – the situation we're in after reading, say, 1110 is identical to the situation we're in after reading 10, except that we've output two bits already (but there's no need to remember which two bits they were, because those never become relevant later).
Ending the program
@``aaqbjFLlljdlLDDdEDLHJJBBbd`bK[GGEGFFB@@HIIKAIMMAEMkKJHzz{{kAakjz[[{qq
`` bd`
aa kAa
q qq
Eventually, we reach the end of the input, causing an end-of-file condition. Incident handles end of file by not jumping at all – it just falls through from the input instruction to the next instruction. To convert binary to Gray codes, we need to handle this by outputting a copy of the most recently input bit (because the most significant bit of the input is output directly in addition to being XORed with the bit below), then quitting the program.
If the most recently read bit was a 0 bit, so we're using b to read input, then we fall through to d (which outputs 0 bits), then use ` to jump back to the start of the program. Likewise, if we read a 1 bit and thus used k to read input, we fall through to A to output a 1 bit and a to jump back to the start of the program. In either case, q jumps to the end of the program and exits.
This code is a little inefficient – I was a little safer than I needed to be here. Normally in Incident, you have to jump backwards to reach the same point from two different places, because forward jump labels don't behave properly if encountered directly (they either try to read input or return from a subroutine, depending on whether they've been used before or not). In the version of the program with comments removed, you could save three bytes via using forward jumps to the end of the program, rather than needing a separate q – this would mean encountering a forward jump label, but because the corresponding jump would never have been used, it would try to read input, encounter the same end-of-file condition again, and fall through, so the "forbidden control merge" would actually work in this case. I'm not sure whether that would translate to byte savings in the restricted-source version of the program, though, and it'd require redoing the whole program to find out, so I'm happy with what I have at the moment.