This post was inspired by my brief subscription last year to HackerRank practice coding challenges by email. It was like a getting an entire lower-division CS homework assignment every week again, for better or worse. Most of the problems in the easy-to-medium ratings are quickly solved in C, less obviously implemented in hand-rolled assembly code, but one in particular seemed amenable to the 6809 addressing modes.

My impetus to pick up 6809 code had in turn been inspired by a few things, in chronological order:

  1. returning to a former employer in 2013 and noticing the MC6809 DIPs stocked for lab used had not yet depleted from the most recent (but likely decades old) order
  2. printing the datasheet and discovering it had several 16-bit registers
  3. listening to the CoCo Crew Podcast and the hosts’ discussion of position-independent code on the Color Computer

Here is my official solution in C to the Funny String problem, where the problem defines a funny string as one in which the set formed by calculating absolute alphabetical distance between every two successive letters in the string is the same for the reversed string.  The example for the problem illustrates “acxz” as funny (because its difference set {2, 21, 2} is symmetric) and “bcxz” as not funny (because its set {1, 21, 2} is not).

void print_funny(const char* string) {
  int a;
  const char* x;
  const char* y;

  a = strlen(string);
  if (a > 1) {
    x = string+0;
    y = string+a;
    for (a = (a+1)/2; a; a--) {
      int b = *--y;
      b -= *(y-1);
      b = (b >= 0) ? b : -b;
      {
        int refdif = b;
        b = *x++;
        b -= *x;
        b = (b >= 0) ? b : -b;
        if ((b -= refdif) != 0) {
          printf("Not ");
          break;
        }
      }
    }
  }
  printf("Funny\n");
}

A similar implementation for the CoCo running Extended Color BASIC just needs to:

  1. find the string from the USRn() call, pointing X at the first character or quitting with an error code of -1 if the argument is too short (or not a string at all)
  2. grab the string length from the BASIC structure, setting Y to the final character and iterating through the following loop half as many times (rounded down since an odd-length string will just leave a difference in the center that will match itself) so that X and Y meet in the middle
  3. for every pair of two adjacent characters at/after X and at/after Y, compare both the differences

Generating the assembly listing file with asm6809 -l funny.lst funny.s shows the total instruction count for the nfunny() function is 29 and byte count is 50. Note the inclusion of a #define FASTDUP flag to optimize the processing of repeat letters, e.g. whitespace, which adds 6 instructions totalling 11 bytes but reducing those iterations from 55 cycles to just 39:

nfunny ldb  #$ff  ;register int16_t nfunny(register uint1_t a,
       tsta       ;                        register uint8_t* x) {
       beq  6f    ;
       lda  ,x    ;  if (a && (x[0] > 1)) { // x: string struct
       bita #$fe  ;    register uint8_t a = x[0]; // a: strlen, >= 2
       beq  6f    ;    register uint8_t* xp = x; // x: &string[0]
       leax [2,x] ;    register int8_t* x = *((int8_t**)xp + 2);
       leay a,x   ;    register int8_t* y = x+a; // y: &string[a]
       inca       ;
       lsra       ;    for (a = (a + 1)/2; a; a--) { // process half

1      ldb  ,-y   ;      register int8_t b = *--y;
       subb -1,y  ;      b -= *(y-1);
       bpl  2f    ;
       comb       ;
       incb       ;      b = (b >= 0) ? b : -b;
if FASTDUP        ;#if defined(FASTDUP)
2      bne  2f    ;      if (b == 0) { // quicker compares but larger
       ldb  ,x+   ;        b = *x++;
       subb ,x    ;        b -= *x;
       beq  4f    ;        if (b == 0) continue;
       clra       ;        else return b & 0x00ff;
       bra  7f    ;      } else
endif             ;#endif
2      stb  ,-s   ;      { // duplicates not optimized but short code
       ldb  ,x+   ;        uint8_t refdif = b;
       subb ,x    ;
       bpl  3f    ;        b = *x++;
       comb       ;        b -= *x;
       incb       ;        b = (b >= 0) ? b : -b;
3      subb ,s+   ;        if ((b -= refdif) != 0) // mustn't be funny
       bne  5f    ;          return b & 0x007f;
4      deca       ;      }
       bne  1b    ;    }
       clrb       ;    return 0; // confirmed to be funny
5      andb #$7f  ;  } else
6      sex        ;    return -1; // string invalid or too short
7      jmp  $b4f4 ;}

In the wild, and certainly depending on the language, enough strings will have sequential duplicate characters that the 11 extra bytes will be affordable.  The return value in the double-width accumulator will be passed back to Extended Color BASIC by the jump to the ROM routine at $b4f4:

  • -1, if the string is zero-length
  • 0, if the string is funny
  • >0, if the string is not funny

So the ECB program becomes (assuming the above routine was loaded at $2800):

200 DEFUSR1=&H2800
210 INPUT A$
220 IF USR1(A$)<>0 PRINT "NOT ";
230 PRINT "FUNNY"

 

Advertisements