# A fast generator of palindrome dates in chronological order

02/02/2020 is a palindrome day because reading the date left-to-right or right-to-left still refers to the same calendar date. And because it doesn't matter whether you use the DD/MM/YYYY format or the MM.DD.YYYY format, it's called a Universal Palindrome Day.

No one year can have more than 1 palindrome day. This is important because we need only consider the year to obtain a chronological list through sorting.

In the 10000 year period, that we can express using 4 decimal digits, there are precisely 366 palindrome days.

366 is (31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30 + 31)


Every combination of day and month numbers produces a valid date. No special care has to be taken of the 29th of February since both 2092 (29/02/2092) and 9220 (02.29.9220) will indeed be leap years. Let's hope we're still around...

Combining day and month is done using nested loops. The outer loop necessarily iterates over the month because we can only know the iteration count for the inner loop once we have chosen a month and consulted a lookup table (LUT) to find out how many days that particular month has.

Just combining alone will not produce the sought for chronological order. Ordinarily we would sort the outputs from the combining operation, but I've discovered that sorting the inputs to the combining part can be much faster. Even faster than producing an unsorted list! Moreover, where sorting the outputs heavily depends on the quality of the chosen sort method, sorting the inputs does not (much). My code never has to sort more than 31 values.

I could easily have opted to not sort at all, if only I would have used more lookup tables. The trouble with lookup tables is to know when enough is enough. The extreme being one big lookup table with the final results at the ready. Where's the fun in that?
That's not to say that I've not explored it: replacing the 70 code bytes in PALINDR1.ASM_Part1 with the 214 bytes of 4 embedded lookup tables will bring the execution time down from 5.4 µsec to 3.0 µsec.

  5.4 µsec PALINDR1.ASM Sorted inputs
6.9 µsec PALINDR2.ASM Unsorted
111.8 µsec PALINDR3.ASM Sorted outputs


Of course these timings don't include the int 21h DOS.PrintString call.

; PALINDR1.ASM (c) 2020 Sep Roland
; --------------------------------
; assemble with FASM

ORG     256

; This program lists all palindrome days according to DD/MM/YYYY
; It sorts the inputs to obtain a chronological list

; Part 1 fills 4 ordered tables with the reversed textual representations
; of months and days
push    31 30 29 12             ; (1)
mov     bp, 1010'1101'0101b     ; LUT DaysPerMonth (1 is 31, 0 is less)
mov     di, T12
mov     bx, 1
NextT:  pop     dx                      ; (1) -> DX={12,29,30,31}
push    di                      ; (2) DI points behind a sentinel zero
lea     cx, [bx-1]
rep movsw                       ; Copy the mother table
mov     cl, 10                  ; CONST
.Next:  mov     ax, bx
div     cl
add     ax, 3030h
shr     bp, 1                   ; Hiding the DaysPerMonth info
rcl     ax, 1                   ; ... in bit 0
add     di, 2
push    di                      ; (3)
.Sort:  mov     [di], si                ; Garbage the 1st time
sub     di, 2
mov     si, [di-2]              ; This could read the sentinel
cmp     si, ax
jg      .Sort
mov     [di], ax
pop     di                      ; (3)
inc     bx
cmp     bx, dx
jbe     .Next
xor     ax, ax                  ; Zero terminator on each table is at
stosw                           ; the same time sentinel of next table
pop     si                      ; (2) New table is mother of next table
cmp     dx, 31
jb      NextT

; Part 2 makes all the valid month and day combinations (366 in all)
mov     si, T12
lodsw
shr     ax, 1                   ; -> CF (*) Extract DaysPerMonth info
; The outer loop updates the month and century fields
Outer:  push    si                      ; (4)
mov     si, T12+(12+1+29+1+30+1)*2 ; Point at T31
jc      .a                      ; (*) OK, 31 days
sub     si, (30+1)*2            ; Point at T30
cmp     ax, "02"                ; Is it February ?
jne     .a                      ; No, 30 days
sub     si, (29+1)*2            ; Point at T29, 29 days
.a:     mov     [String+3], ax          ; 2-digit month
mov     [String+6], ah          ; 2-digit century
mov     [String+7], al

lodsw
shr     ax, 1
; The inner loop updates the day and year fields
Inner:  mov     [String+0], ax          ; 2-digit day
mov     [String+8], ah          ; 2-digit year
mov     [String+9], al
mov     dx, String
mov     ah, 09h                 ; DOS.PrintString
int     21h
lodsw
shr     ax, 1                   ; No info to extract, but
jnz     Inner                   ; ... used as iterator test

pop     si                      ; (4)
lodsw
shr     ax, 1                    ; -> CF (*) Extract DaysPerMonth info
jnz     Outer

mov     ax, 4C00h                ; DOS.Terminate
int     21h
; --------------------------------------
String: db      '../../....', 13, 10, '$' ALIGN 2 dw 0 ; Sentinel T12: rw 12+1+29+1+30+1+31+1  For comparison here are the unsorted and post-sorted DD/MM/YYYY versions: ; PALINDR2.ASM (c) 2020 Sep Roland ; -------------------------------- ; assemble with FASM ORG 256 ; This program lists all palindrome days according to DD/MM/YYYY ; It does not produce a chronological list ; The code makes all the valid month and day combinations (366 in all) xor si, si ; Month ; The outer loop updates the month and century fields Outer: mov cl, [MDays+si] ; LUT DaysPerMonth inc si mov ax, si aam add ax, "00" mov [String+6], ax ; 2-digit century mov [String+3], ah ; 2-digit month mov [String+4], al xor di, di ; Day ; The inner loop updates the day and year fields Inner: inc di mov ax, di aam add ax, "00" mov [String+8], ax ; 2-digit year mov [String+0], ah ; 2-digit day mov [String+1], al mov dx, String mov ah, 09h ; DOS.PrintString int 21h dec cl ; Next day jnz Inner cmp si, 12 ; Next month jb Outer mov ax, 4C00h ; DOS.Terminate int 21h ; -------------------------------------- String: db '../../....', 13, 10, '$'
MDays:  db      31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

; PALINDR3.ASM (c) 2020 Sep Roland
; --------------------------------
; assemble with FASM

ORG     256

; This program lists all palindrome days according to DD/MM/YYYY
; It sorts the outputs to produce a chronological list

; Part 1 creates an ordered list of palindrome years
xor     dx, dx                  ; Table size
xor     si, si                  ; Month
; The outer loop inserts the reversed textual representation of the month
; as the most significant part of the 4-byte string in EBX
; e.g. for February - EBX=5048____h (EBX="__02")
Outer:  mov     cl, [MDays+si]          ; LUT DaysPerMonth
inc     si
mov     ax, si
aam
add     ax, "00"
xchg    al, ah
mov     bx, ax
shl     ebx, 16

xor     di, di                  ; Day
; The inner loop inserts the reversed textual representation of the day
; as the least significant part of the 4-byte string in EBX
; e.g. for 1 February - EBX=50484948h (EBX="0102")
Inner:  inc     di
mov     ax, di
aam
add     ax, "00"
xchg    al, ah
mov     bx, ax

; MergeSorting EBX into the growing table
; e.g. EBX=50484948h (EBX="0102") corresponds to the year 2010
mov     bp, dx
Look:   mov     eax, [Table+bp-4]       ; This could read the sentinel
cmp     eax, ebx
jb      Found
mov     [Table+bp], eax
sub     bp, 4
jnz     Look
Found:  mov     [Table+bp], ebx         ; Add new element
add     dx, 4                   ; The array grows

dec     cl                      ; Next day
jnz     Inner

cmp     si, 12                  ; Next month
jb      Outer

; Part 2 displays the whole list of completed palindrome days
mov     si, Table
mov     di, String
mov     dx, di
Show:   lodsd
mov     [di], ax                ; 2-digit day
bswap   eax
mov     [di+3], ah              ; \ 2-digit month
mov     [di+4], al              ; /
mov     [di+6], eax             ; 4-digit year
mov     ah, 09h                 ; DOS.PrintString
int     21h
cmp     si, Table+366*4
jb      Show

mov     ax, 4C00h               ; DOS.Terminate
int     21h
; --------------------------------------
String: db      '../../....', 13, 10, '$' MDays: db 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 ALIGN 4 dd 0 ; Sentinel Table: rd 366  ## Final note on the MM.DD.YYYY format (not shown) Quoting one paragraph: Combining day and month is done using nested loops. The outer loop necessarily iterates over the month because we can only know the iteration count for the inner loop once we have chosen a month and consulted a lookup table (LUT) to find out how many days that particular month has. This constraint is of no importance for the unsorted and post-sorted MM.DD.YYYY versions, but for the pre-sorted MM.DD.YYYY version I don't see any way around it. Any ideas? • All US-format palindrome dates are all ISO-8601-format palindrome dates, of course. Feb 25, 2020 at 15:45 ## 1 Answer ## This program lists all palindrome days according to MM.DD.YYYY. The code makes all the valid month and day combinations (366 in all). It uses 4 pre-sorted lookup tables (embedded for speed) to obtain a chronological list. In the MM.DD.YYYY format the most significant part of the year YYYY reflects in the day DD. This will be used for the outer loop. The outer loop runs through the T31 list so as to process all the possible day numbers. In the MM.DD.YYYY format the least significant part of the year YYYY reflects in the month MM. This will be used for the inner loop. However the number of iterations will vary depending on the day value being greater (a), equal (b) or smaller (c) than 30: (a).The inner loop runs through the T7 list when the outer loop processes the day number 31. Stored as '31'. (b).The inner loop runs through the T11 list when the outer loop processes the day number 30. Stored as '30'. (c).The inner loop runs through the T12 list for every other day number that the outer loop processes. The T31 list is an ordered list of the 2-characters ASCII representation of the numbers in the range [1,31]. The T12 list is an ordered list of the 2-characters ASCII representation of the numbers in the set {1,2,3,4,5,6,7,8,9,10,11,12}. Months that have 29+ days. (For the purpose of this program February has 29 days.) The T11 list is an ordered list of the 2-characters ASCII representation of the numbers in the set {1,3,4,5,6,7,8,9,10,11,12}. Months that have 30+ days. The T7 list is an ordered list of the 2-characters ASCII representation of the numbers in the set {1,3,5,7,8,10,12}. Months that have 31 days.  2-chars List List Number ASCII Entry Order --------------------------------- 1 -> '01' -> 3130h 4th 2 -> '02' -> 3230h 8th 3 -> '03' -> 3330h 11th 10 -> '10' -> 3031h 1st 11 -> '11' -> 3131h 5th 12 -> '12' -> 3231h 9th 20 -> '20' -> 3032h 2nd 21 -> '21' -> 3132h 6th 22 -> '22' -> 3232h 10th 30 -> '30' -> 3033h 3rd 31 -> '31' -> 3133h 7th  The chronological ordering of the final result, which demands digits reversal, comes naturally from sorting these text-based tables.  mov si, T31 lodsw Outer: push si mov si, T7 cmp ax, "31" je @f mov si, T11 cmp ax, "30" je @f mov si, T12 @@: mov [String+3], ax ;Day mov [String+6], ah ;Century mov [String+7], al lodsw Inner: mov [String], ax ;Month mov [String+8], ah ;Year mov [String+9], al mov dx, String mov ah, 09h ;Print string int 21h lodsw test ax, ax jnz Inner pop si lodsw test ax, ax jnz Outer mov ax, 4C00h ;Exit to DOS int 21h ALIGN 2 T7: db '10011203050708' dw 0 T11: db '1001111203040506070809' dw 0 T12: db '100111021203040506070809' dw 0 T31: db '10203001112131021222031323041424051525061626071727081828091929' dw 0 String: db '..........',13,10,'$'