News for hackers. Stuff that matters.
Re:Banned C standard library functions in Git source code by valleyer on Monday August 26, 2019 @01:35AM (#20797660)
This was super fun to decipher!

1. The first time through this giant ternary defines 9 different small subroutines. Each subroutine can consider the value of "x" to be their argument. X is used as an index into the jmp_buf (subroutine) array during setup, but after that it's always just equal to 8

2. Subroutines 0, 1, and 2 are special. Their argument is the index of another subroutine to jump to. They mutate the character buffer state and then jump to the specified subroutine

3. Before jumping, subroutine 0 moves back a character, subroutine 1 moves forward a character, and subroutine 2 prints the current character and marks it by setting its high bit. Once a character is marked, it will never be printed again

4. All other subroutines get the current character value as their argument

5. Subroutines 3, 4, 5, 6, 7, and 8 all check, in different ways, whether the current character has been marked: x < 0, x >> 8, x & 0x80, (8 << 5) & x, x & 128, x > 0

6. Execution starts at subroutine 3

So you can annotate the code as:

    // Subroutine 0:
    //   move to next char;
    //   goto x;
    (x=setjmp(j[X++])) ? 
     J(j[x], *++i) :
    
    // Subroutine 1:
    //   move to prev char;
    //   goto x;
    ((x=setjmp(j[X++])) ? 
     J(x[j], *--i) :
    
    // Subroutine 2:
    //   print and mark (set high bit on) curr char;
    //   goto x;
    ((x=setjmp(j[X++])) ?
        J(x[j], (putchar(*i), *i+=128)) :
    
     // Subroutine 4:
     //   if (curr char is marked) {
     //     // goto 1(5);
     //     move to prev char;
     //     goto 5;
     //   } else {
     //     print and mark curr char;
     //     goto 3;
     //   }
     (x=setjmp(j[++X])) ?
        ((x<0) ? J(1[j],5) : J(2[j],3)) :
     
     // Subroutine 5:
     //   if (curr char is marked) {
     //     // goto 1(6);
     //     move to prev char;
     //     goto 6;
     //   } else {
     //     // goto 1(3);
     //     move to prev char;
     //     goto 3;
     //   }
     (x=setjmp(j[++X])) ?
        ((x >> X) ? J(1[j], 6) : J(1[j], 3)) :
     
     // Subroutine 6:
     //   if (curr char is marked) {
     //     // goto 1(7);
     //     move to prev char;
     //     goto 7;
     //   } else {
     //     // goto 1(5);
     //     move to prev char;
     //     goto 5;
     //   }
     (x=setjmp(j[++X])) ?
        ((x & 0x80) ? J(1[j], 7) : J(1[j], 5)) :
     
     // Subroutine 7:
     //   if (curr char is marked) {
     //     // goto 1(4);
     //     move to prev char;
     //     goto 4;
     //   } else {
     //     print and mark curr char;
     //     goto 8;
     //   }
     (x=setjmp(j[++X])) ?
        (((X << 5) & x) ? J(1[j], 4) : J(2[j], X)) :
     
     // Subroutine 8:
     //   if (curr char is marked) {
     //     // goto 0(8);
     //     move to next char;
     //     goto 8;
     //   } else {
     //     print and mark curr char;
     //     goto 4;
     //   }
     (x=setjmp(j[++X])) ?
        ((x & 128) ? J(0[j], X) : J(2[j], 4)) :
     
     // Subroutine 3:
     //   if (curr char is not marked) {
     //     print and mark curr char;
     //     goto 6;
     //   } else {
     //     exit;
     //   }
     (setjmp(j[3])>=0) ?
        J(j[2],6) : 0));
    
    // X = 8
    // goto 3(0);
A more straightforward way of writing this would be

    #define IS_CURR_CHAR_MARKED() (*i < 0)
    #define PRINT_AND_MARK_CURR_CHAR() do { putchar(*i); *i += 128; } while (0)
    int curr_sub = 3;
    
    for (;;) {
        switch (curr_sub) {
            case 3:
                if (!IS_CURR_CHAR_MARKED()) {
                    PRINT_AND_MARK_CURR_CHAR();
                    curr_sub = 6;
                } else {
                    return 0;
                }
                break;
            case 4:
                if (IS_CURR_CHAR_MARKED()) {
                    i--;
                    curr_sub = 5;
                } else {
                    PRINT_AND_MARK_CURR_CHAR();
                    curr_sub = 3;
                }
                break;
            case 5:
                if (IS_CURR_CHAR_MARKED()) {
                    i--;
                    curr_sub = 6;
                } else {
                    i--;
                    curr_sub = 3;
                }
                break;
            case 6:
                if (IS_CURR_CHAR_MARKED()) {
                    i--;
                    curr_sub = 7;
                } else {
                    i--;
                    curr_sub = 5;
                }
                break;
            case 7:
                if (IS_CURR_CHAR_MARKED()) {
                    i--;
                    curr_sub = 4;
                } else {
                    PRINT_AND_MARK_CURR_CHAR();
                    curr_sub = 8;
                }
                break;
            case 8:
                if (IS_CURR_CHAR_MARKED()) {
                    i++;
                    curr_sub = 8;
                } else {
                    PRINT_AND_MARK_CURR_CHAR();
                    curr_sub = 4;
                }
                break;
        }
    }
Re:Banned C standard library functions in Git source code by Lerc on Tuesday August 27, 2019 @03:43AM (#20807146)
That's quite impressive work. It becomes a bit clearer if you think of the string as a tape. Then a big case statement with Left,Right,Mark seems rather Turing complete :-)