Code - Andrew Warren

[home] [environment] [contact] [for sale] (code) [cars] [links] [essays]

tiny encryption algorithm

Strong cryptography is classified as a munition by the United States statute which places export restrictions on munitions.

That statute contains an exemption for material which is freely available in public libraries, but it's still unclear whether anonymous ftp sites and web pages qualify as "public libraries".

Therefore, I must ask non-US users of this site not to download these files, since they contain software which could be construed to fall under US export-control law.

Download TEA16.ZIP
View TEA16.TXT

Download TEA17.ZIP
View TEA17.TXT

The Tiny Encryption Algorithm (TEA) was developed by David Wheeler and Roger Needham at the Computer Laboratory of Cambridge University.

It's very fast when implemented on 32-bit machines with barrel shifters, and even on the Microchip PIC16 -- an 8-bit accumulator-based microcontroller with neither a barrel shifter nor even an "add with carry" instruction -- it's no slouch.

Performance specs for my implementations:

	`RAM`	`ROM`	`SPEED`
`TEA16`	`40 bytes`	`295 words`	`6K bytes/sec @ 20 Mhz`
`TEA17`	`37 bytes`	`192 words`	`12K+ bytes/sec @ 33 MHz`

A PIC18 version is in the works, and it'll be available here as soon as Microchip publicly releases the PIC18 instruction set.

The TEA algorithm has been released to the public domain. More information on the algorithm is available from the University of Bradford's Cryptography & Computer Communications Security Group, at http://vader.brad.ac.uk/tea/tea.shtml.

bcd clock

Thanks to Scott Dattalo for his assistance in making this routine as small as it is.

This little routine, which will run on any of the Microchip PICs including the 12-bit parts, maintains a clock whose variables are stored in packed-BCD format [that is, the numbers in the table below are hexadecimal].

Call it once per second, and it'll adjust HOURS, MINUTES, and SECONDS as shown in the table below. As an added bonus, it'll return with the carry flag set when the HOURS register rolls over from 23 to 00.

Before calling `TICK`			After calling `TICK`
`HOURS`	`MINUTES`	`SECONDS`	`HOURS`	`MINUTES`	`SECONDS`
`09`	`00`	`00`	`09`	`00`	`01`
`09`	`59`	`59`	`10`	`00`	`00`
`23`	`59`	`59`	`00`	`00`	`00`

SECONDS EQU     [any register, on any page]
MINUTES EQU     SECONDS+1
HOURS   EQU     MINUTES+1

TICK:   MOVLW   SECONDS
        MOVWF   FSR
        CALL    SUB1
        CALL    SUB0
        CALL    SUB0
        GOTO    SUB2

SUB0:   INCF    FSR
        SKPNC
SUB1:   INCF    INDF

        MOVLW   6
        ADDWF   INDF
        SKPDC
        SUBWF   INDF

        MOVLW   0100H - 060H
SUB2:   ADDWF   INDF,W
        SKPNC
        CLRF    INDF

RETLW 0100H - 024H

day of the week

Want to mentally calculate the day of the week for any month, day, and year?

Here's how:

Just remember that, in any given year, the following nine dates all fall on the same day of the week:

4/4 These should be easy to remember

6/6

8/8

10/10

7/11 These can be remembered by the mnemonic, "I work at the 7-11, from 9 to 5."

11/7

9/5

5/9

last day of February Either the 28th or 29th, depending

In 1998, those nine dates all fall on Saturday. Every year, this day advances by one, unless the year is a leap year, in which case it advances by two.

That is... These nine dates will all fall on Sunday in 1999, on Tuesday in 2000 (because 2000 is a leap year), on Wednesday in 2001, on Thursday in 2002, etc.

Now... If someone asks you, "Quick! What day is August 2, 1999?", you'd think, "Hmm... 8/8 is a Saturday this year, so it'll be a Sunday next year, and six days before that would be, umm...", and answer "Monday!"

With a little practice, you'll find that you can come up with the day of the week in just a few seconds, for any date within a few years of today.

Since you know that the day of the week advances by five days every four years, you can easily calculate the day-of-the-week for years further in the past and future, too.

The only thing you'll have to remember, if you're asked to prove that you're some sort of Rainman-esque idiot savant by calculating the day of the week for dates in other centuries, is that century years are only leap years if they're divisible by 400. That is, 2000 is a leap year, but 1700, 1800, 1900, and 2100 aren't.

That last bit is complicated, so if it were me, I'd answer those "Rainman" challenges with: "What do you think I am... An idiot savant or something?"

Here's a little routine that'll calculate the day of the week for any date between 1 January 1995 and 31 December 2094:

DAY     EQU     [any register]
MONTH   EQU     [any register]
YEAR    EQU     [any register]
DOW     EQU     [any register]

; FOR ANY DATE BETWEEN JANUARY 1 1995 AND DECEMBER 31 1994,
; CALCULATE THE DAY OF THE WEEK [0=SUNDAY, 1 = MONDAY,
; .... 6 = SATURDAY].
;
; ENTER WITH MONTH [1-12] IN "MONTH", DAY-OF-MONTH [1-X]
; IN "DAY", AND YEAR [95-99, 00-94] IN "YEAR". IF "YEAR"
; IS LESS THAN 95, THIS SUBROUTINE ASSUMES THAT WE'RE IN
; THE 21ST CENTURY. OTHERWISE, IT ASSUMES THAT WE'RE IN
; THE 20TH.
;
; ON EXIT, DAY-OF-WEEK IS IN "DOW". "DAY", "MONTH", AND
; "YEAR" ARE UNCHANGED.

DAYWEEK:

; THE FOLLOWING TWO LINES ARE ONLY NECESSARY IF YOU'RE
; USING A 14-BIT PIC (16C6X, 16C7X, 16C8X, ETC.). FOR
; ALL OTHER PICS, JUST MAKE SURE THAT THE "MONTHTBL"
; SUBROUTINE IS ENTIRELY CONTAINED IN PAGE 0.

MOVLW HIGH MONTHTBL ;MAKE SURE THE "ADDWF PCL"
MOVWF PCLATH ;IN "MONTHTBL" WORKS.

        DECF    MONTH,W         ;W = MONTH - 1.
        CALL    MONTHTBL        ;LOOKUP THE D-O-W FOR THE
                                ;1ST OF THIS MONTH.

MOVWF DOW ;STORE IT.

; AGAIN, THE FOLLOWING TWO LINES ARE ONLY NECESSARY FOR
; PARTS THAT USE "PCLATH".

MOVLW $+2 ;RESTORE PCLATH.
MOVWF PCLATH ;

        MOVLW   3               ;MONTH >= MARCH?
        SUBWF   MONTH,W         ;
        BNC     NOLEAP          ;IF NOT, JUMP AHEAD.

MOVLW 00000011B ;OTHERWISE, IS THIS A
ANDWF YEAR,W ;LEAP YEAR?

BNZ NOLEAP ;IF NOT, JUMP AHEAD.

; IT'S MARCH 1ST OR LATER, AND THIS YEAR'S A LEAP YEAR.

INCF DOW ;ADD A LEAP DAY.

NOLEAP:

        CLRC                    ;DOW = DOW + (YEAR-1)/4
        RLF     DOW             ;
        DECF    YEAR            ;    = 2*DOW + (YEAR-1)/2
        RLF     YEAR,W          ;      ------------------.
        RRF     YEAR,W          ;              2
        INCF    YEAR            ;
        ADDWF   DOW             ;
        CLRC                    ;
        RRF     DOW             ;

        MOVF    DAY,W           ;DOW = DOW + DAY + YEAR.
        ADDWF   YEAR,W          ;
        ADDWF   DOW             ;

        MOVLW   95              ;YEAR < 95?
        SUBWF   YEAR,W          ;
        SKPC                    ;IF NOT, SKIP AHEAD.

DECF DOW ;OTHERWISE, DOW = DOW - 1.

        MOVLW   7               ;DOW = DOW MOD 7.
                                ;
        SUBWF   DOW             ;
        SKPNC                   ;
        GOTO    $-2             ;
                                ;
        ADDWF   DOW             ;

        RETURN                  ;RETURN. IF YOU'RE USING
                                ;A 12-BIT PIC, MAKE THIS A
                                ;"RETLW 0" OR SOMETHING.

MONTHTBL:

ADDWF PCL

        DT      7,10,10,13      ;DAY-OF-WEEK FOR FIRST DAY
        DT      8,11,13,9       ;OF EACH MONTH (IN YEAR
        DT      12,7,10,12      ;1995). 7=SUNDAY, 8=MONDAY,
                                ;...., 13=SATURDAY.

minimum

Thanks to John Payson for the idea on which this routine is based.

Given three values stored in registers NUM1, NUM2, and NUM3, this
routine finds the minimum value and stores it in RESULT, leaving
NUM1, NUM2, and NUM3 unchanged.

9 words, 9 instruction cycles.

;NOTE: In the comments below, "min(A,B)" means "the lesser ; of A and B".

MOVF NUM1,W ;Set the Carry flag if NUM1 is less
SUBWF NUM2,W ;than NUM2.

        MOVF    NUM1,W ;Assume that NUM1 was less than
                        ;NUM2. This instruction does NOT
                        ;affect the Carry flag.

SKPC ;If NUM1 really was less than NUM2,
;skip ahead with W = NUM1.

MOVF NUM2,W ;Otherwise, W = NUM2.

;At this point, W contains min(NUM1,NUM2).

MOVWF RESULT ;Store it in RESULT.

;At this point, both W and RESULT contain min(NUM1,NUM2).

        SUBWF   NUM3,W ;Set the Carry flag if W [which
                        ;contains min(NUM1,NUM2), remember]
                        ;is less then NUM3.

;At this point, RESULT still holds min(NUM1,NUM2), but W now
;contains NUM3 - min(NUM1,NUM2).

SKPC ;If W really was less than NUM3, skip
;ahead.

        ADDWF   RESULT ;Otherwise,
                        ;RESULT= RESULT + W
                        ;      = min(N1,N2) + W
                        ;      = min(N1,N2) + [N3-min(N1,N2)]
                        ;      = N3.
                        ;

;At this point, RESULT holds min(NUM3,min(NUM1,NUM2)), which ;is of course equivalent to min(NUM1,NUM2,NUM3).

bcd to binary

These routines convert unpacked BCD inputs to binary.

The first one works only on inputs in the range [0-255]; it performs the conversion in 13 cycles on any of the PIC16Cxx parts:

RADIX DEC

; Enter with a BCD number in HUND, TENS, and ONES (one digit
; per register)... We don't care if they're straight numbers
; in the range [0-9] or ASCII values in the range
; [0x30-0x39].
;
; Exits with HUND, TENS, and ONES unchanged, and
; W = (HUND * 100) + (TENS * 10) + ONES.
;
; Note that this routine ONLY works if the input BCD number
; is in the range [0-255].
;
; 13 cycles.

BCD2BIN:

MOVF ONES,W

        BTFSC   TENS,0
        ADDLW   10
        BTFSC   TENS,1
        ADDLW   20
        BTFSC   TENS,2
        ADDLW   40
        BTFSC   TENS,3
        ADDLW   80

        BTFSC   HUND,0
        ADDLW   100
        BTFSC   HUND,1
        ADDLW   200

This one's not quite so elegant, but it's faster; it performs the conversion in 10 cycles:

RADIX DEC

; Enter with a BCD number in HUND, TENS, and ONES (one digit
; per register). Each register (well... TENS, anyway) must
; hold a number in the range [0-9].
;
; Exits with ONES and HUND unchanged, TENS scrambled, and
; W = (HUND * 100) + (TENS * 10) + ONES.
;
; Note that this routine ONLY works if the input BCD number
; is in the range [0-255].
;
; 10 cycles.

BCD2BIN:

        CLRC
        RLF     TENS,W
        SWAPF   TENS
        RRF     TENS
        ADDWF   TENS,W

ADDWF ONES,W

        BTFSC   HUND,0
        ADDLW   100
        BTFSC   HUND,1
        ADDLW   200

If you need to deal with three-digit numbers up to 999, you could do
something like this hideous routine (which I'm providing, because it
amuses me to do so, with no line-by-line comments). It requires 29 cycles:

RADIX DEC

; Enter with a BCD number in HUND, TENS, and ONES (one digit
; per register). Each register (well... TENS, anyway) must
; hold a number in the range [0-9].
;
; Exits with ONES and HUND unchanged, TENS scrambled, and
; HI_BYTE:LO_BYTE = (HUND * 100) + (TENS * 10) + ONES.
;
; This routine works for all BCD inputs in the range
; [000-999].
;
; 29 cycles.

BCD2BIN:

        CLRC
        RLF     TENS,W
        SWAPF   TENS
        RRF     TENS
        ADDWF   TENS,W

ADDWF ONES,W

BTFSC HUND,0
ADDLW 100

CLRF HI_BYTE

        BTFSC   HUND,1
        ADDLW   200
        RLF     HI_BYTE

        BTFSC   HUND,2
        ADDLW   LOW (400)
        RLF     HI_BYTE

BTFSC HUND,3
ADDLW LOW (800)

MOVWF LO_BYTE

        MOVLW   00000001
        ANDWF   HI_BYTE,W
        BTFSC   HI_BYTE,1
        ADDLW   1
        SKPNC
        ADDLW   1

BTFSC HUND,2
ADDLW HIGH (400)

BTFSC HUND,3
ADDLW HIGH (800)

MOVWF HI_BYTE

go to the SiliconValley GeoPage