Algorithm to convert integer between bases using LC-3 Assembly Language

Question

I've been trying to figure out a solution to for the last few days. I'm trying to write an algorithm to convert an input integer from base 10 to base 6 using LC-3 assembly language.

I have 2 questions:

1. How can I take user input that's more than just 1 character? Since the GETC command only take 1 character.
2. How would I go about converting down to the smaller base when I only have addition at my disposal?

Answer 1

There may be a tricky algorithm I'm not aware of, but a straightforward one is to read the string of base 10 digits to build a single integer then print it in base 6. The algorithm for reading is pretty simple. I'll code in assembler-like C:

val = 0;
get_next_char:
  ch = getchar();  // use TRAP to get character in LC-3
  if (ch == '\r') goto done_reading;
  val = 10 * val + (ch - '0');
  goto get_next_char;
done_reading:

How to multiply by 10 in LC-3? Note 10 * val == (val << 3) + (val << 1). In turn, val << 1 is just val + val. So we have

t2 = val + val;
t4 = t2 + t2;
t8 = t4 + t4;
t10 = t8 + t2

You can use this basic idea to multiply by any constant. Just build the powers of 2 you need (corresponding to 1's in the multiplicand) and add them up.

Edit I'll give one example to show how this translates to LC-3 assembler. LC-3 is unfamiliar to me, and I don't have an assembler, so have mercy on mistakes:

               ; Load negative of <Enter> character in R1
               LD R1, NEG_ASCII_ENTER
               ; Load negative of '0' character value in R2
               LD R2, NEG_ASCII_ZERO
               ; Use R3 as val.
               AND R3, R3, #0
get_next_char  TRAP x20 ; Getc into R0
               TRAP x21 ; Put character to console.
               ADD R4, R0, R1
               BRz done_reading
               ; Multiply old value of R3 by 10
               ADD R5, R3, R3 ; R5 = 2 * R3
               ADD R6, R5, R5 ; R6 = 4 * R3
               ADD R6, R6, R6 ; R6 = 8 * R3
               ADD R3, R5, R6 ; R3 = 10 * R3
               ADD R3, R0, R2 ; Add actual digit value converted from ASCII
               BR get_next_char
done_reading   ; here B3 has base 10 value read from console

Now to print in base 6. Here we need to compute the characters one at a time and print in reverse. Lots of ways to do this, but here is one:

i = 0;
next_digit:
  if (val == 0) goto done_base_6_conversion;
  digit[i] = (val % 6) + '0';
  i++;
  val = val / 6;
done_base_6_conversion:
  if (i > 0) goto print_buffer;
  putchar('0'); // TRAP for character output
  goto done_printing;
print_buffer:
  i--;
  putchar(digit[i]);
  if (i > 0) goto print_buffer;
done_printing:

The array digit is just a small buffer to hold the base-6 output.

How to subtract? Implement 2s complement negation -x == ~x + 1. To decrement by 1, we add 0xffff.

How about division and mod by 6? It turns out we can do both of these at the same time. The idea is to try subtracting the largest possible power of 2 times 6. If the result is non-negative, add that power of 2 to the initially zero result. If negative, undo the subtraction. Then try each successive lower power until what's left is less than 6. This is the mod. Here is pseudo-C to divide val by 6 and also compute the remainder:

r = 0;
p = mask_table; // p is an address (pointer)
goto test_for_next;
next_trial_subtraction:
  t = *p;
  u = val - t
  if (u < 0) goto set_one;
    p = p + 2 * sizeof(int);
  goto test_for_next;
set_one:
    val = u;
    p = p + sizeof(int);
    r = r + *p;
    p = p + sizeof(int);
test_for_next:
  if (val >= 6) goto next_trial_subtraction;

At the end, r holds the division result and val holds the remainder.

What goes in the mask table? In C it would be this:

int mask_table[] = {
  6 << 13, 1 << 13, 6 << 12, 1 << 12, 6 << 11, 1 << 11,
  6 << 10, 1 << 10, 6 <<  9, 1 <<  9, 6 <<  8, 1 <<  8, 
  6 <<  7, 1 <<  7, 6 <<  6, 1 <<  6, 6 <<  5, 1 <<  5,
  6 <<  4, 1 <<  4, 6 <<  3, 1 <<  3, 6 <<  2, 1 <<  2,
  6 <<  1, 1 <<  1, 6      , 1 };

The reason for starting with 13 is that 6 has three significant bits, so a shift of 13 produces 2^13 * 6, which is the biggest possible, since LC-3 is a 16 bit machine as I recall. If you had bigger integers, you'd need a bigger table. if you had right shift, you could avoid the table altogether.

Note in the code I've subtracted the positive table value, but you'd really want to store the 2s-complement negative and add.

Getting all this into LC-3 is a good exercise, but not so hard. I hope this is helpful.