// Towers of Hanoi
// Solved as a Moore state machine
//
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// We use three integer variables labeled A, B, and C to
// represent the three stacks.  The disks are numbered
// from 1 to NDISK and a set bit "n" in A/B/C indicates
// that disk number n is in that stack.  A cleared bit
// indicates the disk is not in that stack.  The smallest
// disk is in bit 0, and the largest is in bit NDISK-1.
#define NDISK 5
#define USEMASK (uint32_t)0x0000001f

// Variable A is initialized with the low NDISK bits set.
// Note that if a disk is not in A or B then it must be
// in C.  That is C == ~(A | B) for the first NDISK bits.
// The top-of-stack (tos) is the first LSB set.  A stack
// is empty if no bits are set. An invalid disk is set to
// NODISK.
#define NODISK (uint32_t)(0xffffffff)

// For each stack
//   If the tos is even move it clockwise:  A->B->C->A
//   If the tos is odd move it counterclockwise: A->C->B->A
//   Do not move the same piece twice in a row
// Exactly one stack/disk will be a valid move in each pass.

// The idea of odd or even top-of-stack requires comparing
// the value from getlsb() with a mask for ODD.
#define ODDMASK  (uint32_t)0xaaaaaaaa
#define EVENMASK (uint32_t)0x55555555

// The getlsb() macro examines the input integer and 
// replicates just the LSB of the input value.  For example,
// an input of 0x0e46 returns 0x0002.
#define getlsb(inval) \
            ((inval == 0x0000000) ? NODISK :  \
             (inval & 0x00000001) ? 0x00000001 :  \
             (inval & 0x00000002) ? 0x00000002 :  \
             (inval & 0x00000004) ? 0x00000004 :  \
             (inval & 0x00000008) ? 0x00000008 :  \
             (inval & 0x00000010) ? 0x00000010 :  \
             (inval & 0x00000020) ? 0x00000020 :  \
             (inval & 0x00000040) ? 0x00000040 :  \
             (inval & 0x00000080) ? 0x00000080 :  \
             (inval & 0x00000100) ? 0x00000100 :  \
             (inval & 0x00000200) ? 0x00000200 :  \
             (inval & 0x00000400) ? 0x00000400 :  \
             (inval & 0x00000800) ? 0x00000800 :  \
             (inval & 0x00001000) ? 0x00001000 :  \
             (inval & 0x00002000) ? 0x00002000 :  \
             (inval & 0x00004000) ? 0x00004000 :  \
             (inval & 0x00008000) ? 0x00008000 :  \
             (inval & 0x00010000) ? 0x00010000 :  \
             (inval & 0x00020000) ? 0x00020000 :  \
             (inval & 0x00040000) ? 0x00040000 :  \
             (inval & 0x00080000) ? 0x00080000 :  \
             (inval & 0x00100000) ? 0x00100000 :  \
             (inval & 0x00200000) ? 0x00200000 :  \
             (inval & 0x00400000) ? 0x00400000 :  \
             (inval & 0x00800000) ? 0x00800000 :  \
             (inval & 0x01000000) ? 0x01000000 :  \
             (inval & 0x02000000) ? 0x02000000 :  \
             (inval & 0x04000000) ? 0x04000000 :  \
             (inval & 0x08000000) ? 0x08000000 :  \
             (inval & 0x10000000) ? 0x10000000 :  \
             (inval & 0x20000000) ? 0x20000000 :  \
             (inval & 0x40000000) ? 0x40000000 :  \
             (inval & 0x80000000) ? 0x80000000 : NODISK)

// Macro definitions using getlsb() to get top-of-stack values
#define TOSA getlsb(A)
#define TOSB getlsb(B)
#define TOSC getlsb(C)

// Macros for the next move logic
#define A2B ((TOSA & EVENMASK) && (TOSB > TOSA) && (TOSA != last))
#define A2C ((TOSA & ODDMASK) && (TOSC > TOSA) && (TOSA != last))
#define B2C ((TOSB & EVENMASK) && (TOSC > TOSB) && (TOSB != last ))
#define B2A ((TOSB & ODDMASK ) && (TOSA > TOSB) && (TOSB != last))
#define C2A ((TOSC & EVENMASK) && (TOSA > TOSC) && (TOSC != last))
#define C2B ((TOSC & ODDMASK) && (TOSB > TOSC) && (TOSC != last))


int main()
{
    uint32_t A, B, C;               // stacks 
    uint32_t sA, sB, sC;            // shadow stack values
    uint32_t last;                  // last piece moved
    uint32_t slast;                 // shadow of last piece moved
    int      nstep;                 // number of moves taken

    // Initialize variables
    sA = A = USEMASK;
    sB = B = 0;
    sC = C = 0;
    last = NODISK;
    nstep = 0;


    while(1) {
        //printf("%8d   %04x %04x %04x   %x %x %x -- %x\n", nstep,A,B,C,TOSA,TOSB,TOSC,last); 
        //   If the tos is even move it clockwise:  A->B->C->A
        //   If the tos is odd move it counterclockwise: A->C->B->A
        sA = (A2B) ?  A & ~TOSA :    // remove disk from A
             (A2C) ?  A & ~TOSA :    // remove disk from A
             (B2A) ?  A | TOSB :     // put disk on stack A
             (C2A) ?  A | TOSC :     // put disk on stack A
             sA;
        sB = (A2B) ? B | TOSA :      // put disk on stack B
             (B2C) ? B & ~TOSB :     // remove disk from B
             (B2A) ? B & ~TOSB :     // remove disk from B
             (C2B) ? B | TOSC :      // put disk on stack B
             sB;
        sC = (A2C) ? C | TOSA :      // put disk on stack C
             (B2C) ? C | TOSB :      // put disk on stack C
             (C2A) ? C & ~TOSC :     // remove disk from C
             (C2B) ? C & ~TOSC :     // remove disk from C
             sC;
        slast = (A2B) ? TOSA :
                (A2C) ? TOSA :
                (B2C) ? TOSB :
                (B2A) ? TOSB :
                (C2A) ? TOSC :
                (C2B) ? TOSC :
                slast;
        printf("Move %d from %s\n", 
            (A2B) ? TOSA :
            (A2C) ? TOSA :
            (B2C) ? TOSB :
            (B2A) ? TOSB :
            (C2A) ? TOSC :
            (C2B) ? TOSC : NODISK,
            (A2B) ? "A to B" :
            (A2C) ? "A to C" :
            (B2C) ? "B to C" :
            (B2A) ? "B to A" :
            (C2A) ? "C to A" :
            (C2B) ? "C to B" : "Unknown move");

        A = sA;
        B = sB;
        C = sC;
        last = slast;
        nstep++;

        if ((B == USEMASK) || (C == USEMASK)) {
            printf("steps = %d\n", nstep);
            exit(0);
        }

    }
}