// Towers of Hanoi
// Straightforward iterative solution
//
#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 last;                  // last piece moved
    int      nstep;                 // number of moves taken

    // Initialize variables
    A = USEMASK;
    B = 0;
    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
        if (A2B) {
            printf("Move %d from A to B\n", TOSA);
            B = B | TOSA;        // put disk on stack B
            last = TOSA;
            A = A & ~TOSA;       // remove disk from A
        }
        else if (A2C) {
            printf("Move %d from A to C\n", TOSA);
            C = C | TOSA;        // put disk on stack C
            last = TOSA;
            A = A & ~TOSA;       // remove disk from A
        }
        else if (B2C) {
            printf("Move %d from B to C\n", TOSB);
            C = C | TOSB;        // put disk on stack C
            last = TOSB;
            B = B & ~TOSB;       // remove disk from B
        }
        else if (B2A) {
            printf("Move %d from B to A\n", TOSB);
            A = A | TOSB;        // put disk on stack A
            last = TOSB;
            B = B & ~TOSB;       // remove disk from B
        }
        else if (C2A) {
            printf("Move %d from C to A\n", TOSC);
            A = A | TOSC;        // put disk on stack A
            last = TOSC;
            C = C & ~TOSC;       // remove disk from C
        }
        else if (C2B) {
            printf("Move %d from C to B\n", TOSC);
            B = B | TOSC;        // put disk on stack B
            last = TOSC;
            C = C & ~TOSC;       // remove disk from C
        }
        nstep++;

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

    }
}