Score add in C

This is an archive of a topic from NESdev BBS, taken in mid-October 2019 before a server upgrade.
View original topic
Score add in C
by tschak909 on 2017-07-22 (#200664)
This one is putting me in the fetal position, because I am deliberately trying to avoid the division and modulo that is used in the canonical algorithms for converting numbers to an ASCII string, e.g.

Code:
char* itoa(int num, char* str, int base)
{
    int i = 0;
    bool isNegative = false;
 
    /* Handle 0 explicitely, otherwise empty string is printed for 0 */
    if (num == 0)
    {
        str[i++] = '0';
        str[i] = '\0';
        return str;
    }
 
    // In standard itoa(), negative numbers are handled only with
    // base 10. Otherwise numbers are considered unsigned.
    if (num < 0 && base == 10)
    {
        isNegative = true;
        num = -num;
    }
 
    // Process individual digits
    while (num != 0)
    {
        int rem = num % base;
        str[i++] = (rem > 9)? (rem-10) + 'a' : rem + '0';
        num = num/base;
    }
 
    // If number is negative, append '-'
    if (isNegative)
        str[i++] = '-';
 
    str[i] = '\0'; // Append string terminator
 
    // Reverse the string
    reverse(str, i);
 
    return str;
}


Implementing a string to string addition works except when I try to handle the carry, and I've implemented it nine times (yes, I actually am saying this in Ed Rooney's voice), and can't seem to make an algorithm that handles the carry correctly.

I suck atm.

-Thom
Re: Score add in C
by tepples on 2017-07-22 (#200676)
Omegamatrix wrote a 16 bits to 5 digits converter that finishes in less than 200 cycles. It's written in assembly language, but if you ask nicely, someone can adapt its calling convention to work when called from C code compiled by cc65.
Re: Score add in C
by tschak909 on 2017-07-22 (#200681)
tepples wrote:
Omegamatrix wrote a 16 bits to 5 digits converter that finishes in less than 200 cycles. It's written in assembly language, but if you ask nicely, someone can adapt its calling convention to work when called from C code compiled by cc65.


Ah, Omegamatrix is here too. I've known him for over a decade on AtariAge. He hasn't signed on in over a year in either place, it seems...

-Thom
Re: Score add in C
by zzo38 on 2017-07-22 (#200684)
I invented another way (for signed 16-bit numbers into decimal), which however requires many more ROM tables and special pattern tables. I have not compared the speed

However, in some cases you can just work in base 10 or base 100 for scoring anyways and it will work, and you do not need to convert (although you can't use 6502 decimal mode so you have to implement it by yourself instead). (It depends much on the program.)
Re: Score add in C
by tschak909 on 2017-07-22 (#200690)
zzo38 wrote:
I invented another way (for signed 16-bit numbers into decimal), which however requires many more ROM tables and special pattern tables. I have not compared the speed

However, in some cases you can just work in base 10 or base 100 for scoring anyways and it will work, and you do not need to convert (although you can't use 6502 decimal mode so you have to implement it by yourself instead). (It depends much on the program.)


I wound up doing it like this:

Code:
#include <stdio.h>
#include <math.h>

static unsigned char score0[7]={"0000100"};
static unsigned char score1[7]={"0000000"};

static unsigned char i;
static unsigned char a;

/**
 * Add score0 to score1
 */
void add_points(void)
{
  a=0; // clear carry

  // Convert result to binary.
  for (i=6;i-->0; )
    {
      score0[i]=score0[i]-'0';
      score1[i]=score1[i]-'0';
    }

  // Add each piece
  for (i=6;i-->0; )
    {
      score1[i]=score0[i]+score1[i]+a;
      a=(score1[i]>9);
      if (a)
        score1[i]-=10;
    }

  // Convert result back to ASCII
  for (i=6;i-->0; )
    {
      score0[i]=score0[i]+'0';
      score1[i]=score1[i]+'0';
    }
}

void main(void)
{
  for (int q=0;q<1000;++q)
    {
      add_points();
      printf("%c%c%c%c%c%c%c\n",score1[0],score1[1],score1[2],score1[3],score1[4],score1[5],score1[6]);
    }
}


Although, I am altering the ASCII converts, as my number tiles start a 0x01 now.

-Thom
Re: Score add in C
by thefox on 2017-07-23 (#200694)
I spy with my little eye a bug. Your loop should start from i=7 since you decrement in the loop condition. (Which, I have to say, is a very non-standard thing to do, but I think I see why you did it.) Anyway, as it is right now the least significant digit is not handled. I'd also get rid of the binary/ASCII conversions altogether, and simply adjust the comparison in the addition loop. (E.g., if you want to keep using ASCII, generate carry when result > '0'+9.)
Re: Score add in C
by tschak909 on 2017-07-23 (#200699)
Correct on both counts, have fixed this, and will post up in the wiki. :)

-Thom
Re: Score add in C
by lidnariq on 2017-07-23 (#200706)
Have you looked into storing your 'unpacked BCD' representations little-endian? It would let you add different sizes of numbers easily, rather than requiring everything in 6 bytes.
Re: Score add in C
by tschak909 on 2017-07-23 (#200708)
lidnariq wrote:
Have you looked into storing your 'unpacked BCD' representations little-endian? It would let you add different sizes of numbers easily, rather than requiring everything in 6 bytes.


That's a definite possibility, for now it's on my list of crunching bytes to save space.

-Thom