Shortish bitwise method of rouding towards zero to nearest 0x50?

First of all, since 80 = 16 * 5, rounding down to a multiple of 80 means rounding down to a multiple of both 16 and 5. The first one is easy with a right shift, so now we're left with the mod 5 part:

def mod5(x):
    return x % 5

def round80(x):
    x >>= 4
    x -= mod5(x)
    x <<= 4
    return x

mod5 isn't that easy to do, but there is a clever construction for Mersenne moduli that first calculates mod15, and then brings the value down to be modulo 5. It's not that intuitive at first, but it only involves additions and shifts, which should be easy enough to implement. Here's the python version:

def mod15(x):
    x = (x >> 8) + (x & 0xFF)
    x = (x >> 4) + (x & 0xF)
    if x >= 15: x -= 15
    if x >= 15: x -= 15 # (see note)
    return x

def mod5(x):
    x = mod15(x)
    if x >= 5: x -= 5
    if x >= 5: x -= 5
    return x

def round80(x):
    x >>= 4
    x -= mod5(x)
    x <<= 4
    return x

To be safe, I verified this code for all possible values:

for i in range(0x10000):
    trivial = i - (i % 80)
    assert trivial == round80(i)

One additional note: the second if inside of mod15 can actually be omitted for your input range, commenting it out made no difference. If you need the whole [0,0xffff] range, you cannot remove it.

I'm no expert in M6800 assembly so I'm not going to attempt writing the final code, but it should be relatively simple, especially given that the only 16 bit operations are the two shifts and the first addition in mod15.

No division, no multiplication and no lookup tables - I hope this is short enough for your needs!

We take Darios trick and apply it to the limited input range.

As 80 can be divided by 16, we can, in order to round down to the next multiple of 80, discard the rightmost hex digit (set it to zero) and round down the number left of this digit to the next multiple of 5.

That can be done by determining the remainder of such a division and subtracting it. The leftmost digit is a constant 0xE. 0xE00 mod 5 = 4. The second digit is in the hexadecimal system multiplied by 16. 16 mod 5 = 1. So the remainder of the division by 5 is 4 + second digit + third digit.

As we have to shift the input bytes to get to the middle digits and shift back to subtract from the input (or as an alternate way, subtract to and from a shifted number and shift back the difference), we can also do our calculations with numbers shifted to the left, as long as they fit into a byte to save shift operations.

The maximum sum of the two middle digits and 4 is 4 + 0x6 + 0xf = 25. So we can calculate with numbers up to 8x as high to stay below 255.

There are different ways to get the remainder of a division by 5 from a number between 4 and 25. Either by a loop or by a series of tests of the range and branching. (Branches and memory accesses are cheap on those early processors compared to today's.) We have to find a compromise between execution time and code size.

Instead of tests in order to set the flags for branching, we can do actual calculations and branch dependent on the result, which also saves instructions.

The used flags are Carry, Zero and Sign.

Carry/Borrow gives us the information that the previous addition or subtraction went above 255 or below 0 and wrapped around.

Zero/Equal tells us that the result was 0.

Sign gives us the most significant bit, or that the previous sum is actually 16 or higher, if we do all the calculations multiplied by 8. 16*8=128, which is the value of the MSB of an 8 bit unsigned int.

Assuming the index register points to the high byte of the input number followed by the low byte in memory (big endian convention as was often used by Motorola, but the indices can be simply changed in the following code, when accessing memory).

    LDAA #00H,X ; load high byte into A
    ANDA #0FH   ; take lower digit
    LDAB #01H,X ; load low byte into B
    ANDB #F0H   ; select higher digit of B
    ASLA        ; do everything with numbers * 8
    ASLA
    ASLA
    LSRB        ; shift right by 1
    ABA         ; add B to A
    ADDA #20H   ; add 8*4 for contribution of 0xE000
AGAIN:
    SUBA #28H   ; subtract 8*5
    BCC AGAIN   ; no borrow, do it again
    ADDA #28H   ; we subtracted once too much, undo
    ASLA        ; multiply by 2 again
    TAB         ; transfer A to B
    LDAA #01H,X ; load low byte into A
    ANDA #F0H   ; set lower digit to 0
    SBA         ; subtract B from A, keep carry
    STAA #01H,X ; store low byte back
    BCC FINISHED; no borrow occured
    DEC #00H,X  ; borrow -> decrement high byte
FINISHED:

This solution takes 34 bytes and executes up to 30 instructions (and minimally executes 20).

Variant 1:

    LDAA #00H,X ; load high byte into A
    ANDA #0FH   ; take lower digit
    LDAB #01H,X ; load low byte into B
    ANDB #F0H   ; select higher digit of B
    ASLA        ; do everything with numbers * 8
    ASLA
    ASLA
    LSRB        ; shift right by 1
    ABA         ; add B to A
    BPL PLUS0_15; 0..15
    SUBA #(21*8); 16..21 -21
    BCC GOOD    ; 21     change = -21
    ADDA #(5*8) ; 16..20 -21+5
    BRA GOOD    ;        change = -16
PLUS0_15:       ; 0..15
    BNE PLUS1_15; 1..15
    ADDA #(4*8) ; 0      +4
    BRA GOOD    ;        change = +4
PLUS1_15:       ; 1..15
    SUBA #(11*8);        -11
    BCC GOOD    ; 11..15 change = -11
    ADDA #(5*8) ;        -11+5
    BCS GOOD    ; 6..10  change = -6
    ADDA #(5*8) ; 1..5   -11+5+5
                ;        change = -1
GOOD:
    ASLA        ; multiply by 2 again
    TAB         ; transfer A to B
    LDAA #01H,X ; load low byte into A
    ANDA #F0H   ; set lower digit to 0
    SBA         ; subtract B from A, keep carry
    STAA #01H,X ; store low byte back
    BCC FINISHED; no borrow occured
    DEC #00H,X  ; borrow -> decrement high byte
FINISHED:

This solution takes 52 bytes and executes up to 24 instructions (and minimally executes 19). Faster, but larger.

Variant 2:

    LDAA #00H,X ; load high byte into A
    ANDA #0FH   ; take lower digit
    LDAB #01H,X ; load low byte into B
    ANDB #F0H   ; select higher digit of B
    ASLA        ; do everything with numbers * 8
    ASLA
    ASLA
    LSRB        ; shift right by 1
    ABA         ; add B to A
    BPL PLUS0_15; 0..15
    SUBA #(21*8); 16..21 -21
    BRA SAMECODE
    ;BCC GOOD   ; 21     change = -21
    ;ADDA #(5*8); 16..20 -21+5
    ;BRA GOOD   ;        change = -16
PLUS0_15:       ; 0..15
    CMPA #(6*8);
    BCC PLUS6_15; 6..15
    SUBA #(6*8) ;        -1
    BRA SAMECODE
    ;BCC GOOD   ; 1..5   change = -1
    ;ADDA #(5*8); 0      -1+5
    ;BRA GOOD   ;        change = +4
PLUS6_15:       ; 6..15
    SUBA #(11*8);        -11
SAMECODE:
    BCC GOOD    ; 11..15 change = -11
    ADDA #(5*8) ;        -11+5
GOOD:
    ASLA        ; multiply by 2 again
    TAB         ; transfer A to B
    LDAA #01H,X ; load low byte into A
    ANDA #F0H   ; set lower digit to 0
    SBA         ; subtract B from A, keep carry
    STAA #01H,X ; store low byte back
    BCC FINISHED; no borrow occured
    DEC #00H,X  ; borrow -> decrement high byte
FINISHED:

This solution takes 46 bytes and executes up to 24 instructions (and minimally executes 20). A good bit smaller with code reuse, a bit worse optimal case, same worst case. One should better compare the average case.

Variant 3:

    LDAA #00H,X ; load high byte into A
    ANDA #0FH   ; take lower digit
    LDAB #01H,X ; load low byte into B
    ANDB #F0H   ; select higher digit of B
    ASLA        ; do everything with numbers * 8
    ASLA
    ASLA
    LSRB        ; shift right by 1
    ABA         ; add B to A
    BPL PLUS0_15; 0..15
    SUBA #(21*8); 16..21 -21
    BCC GOODA   ; 21     change = -21
    BRA SAMECODE
    ;ADDA #(5*8); 16..20 -21+5
    ;BRA GOODA  ;        change = -16
PLUS0_15:       ; 0..15
    SUBA #(6*8) ;
    BCS PLUS0_5 ; 0..5
    TAB         ; Transfer A to B (keep safe for 6..10)
    SUBA #(5*8) ;        -6-5
    BCC GOODA   ; 11..15 change = -11
    BRA GOODB   ; 6..10 change = -6
PLUS0_5:        ; 0..5
    ADDA #(5*8) ;        -6+5
    BCS GOODA   ; 1..5   change = -1
SAMECODE:
    ADDA #(5*8) ; 0      -6+5+5
                ;        change = +4
GOODA:
    TAB         ; transfer A to B
GOODB:
    ASLB        ; multiply by 2 again
    LDAA #01H,X ; load low byte into A
    ANDA #F0H   ; set lower digit to 0
    SBA         ; subtract B from A, keep carry
    STAA #01H,X ; store low byte back
    BCC FINISHED; no borrow occured
    DEC #00H,X  ; borrow -> decrement high byte
FINISHED:

This solution takes 51 bytes and executes up to 23 instructions (and minimally executes 19). Larger again, but even better worst case.

A more conventional solution (also working with other divisors than 0x50):

    LDAA #00H,X ; load high byte
    SUBA #DCH   ; subtract 0xDC; 0xDC00 is divisible by 80; prevent overflow of counter, shorten execution time; we know input is at least 0xE000
    CLR  #00H,X ; clear counter
    LDAB #01H,X ; load low byte
REP1:
    INC #00H,X  ; count
    SUBB #50H   ; try subtracting 0x50
    SBCA #00H   ; subract with borrow
    BCC REP1    ; not finished
    LDAA #DBH   ; initialize high byte with 0xDB
    LDAB #B0H   ; initialize low byte with 0xB0 (counter is 1 too high)
REP2:
    ADDB #50H   ; add 0x50 to low byte
    ADCA #00H   ; add carry to high byte
    DEC #00H,X  ; decrease counter
    BNE REP2    ; until zero
    STAB #01H,X ; store back low byte
    STAA #00H,X ; store back high byte

This solution needs 32 bytes and executes up to 312 instructions (minimum 112). At least smaller in size.

As comparison the approach with rounding down to multiples of 0x20 instead of of 0x50:

    LDAA #01H,X ; load low byte
    ANDA #E0H   ; zero the 5 low bits
    STAA #01H,X ; store back

would need 6 bytes and execute 3 instructions.

This isn't clever math or bit-twiddling, but you might consider a simple loop if you're optimizing for code space. With your input range there are only 26 possible output values so the worst-case runtime isn't terrible.

#include <stdio.h>
#include <stdint.h>
#include <assert.h>

/* Truncate to nearest multiple of 80, with input range 0xE000 to 0xE7D0. */
uint16_t truncate_to_80(uint16_t n) {
    uint16_t ret = 0xDFC0; /* Lowest possible output. */
    while (ret+80 <= n) {
        ret = ret+80;
    }
    return ret;
}

int main(void) {
    for (int i = 0xE000; i <= 0xE7D0; i++) {
        uint16_t truncated = truncate_to_80(i);
        assert(truncated == (i - (i % 80)));
        printf("%d -> %d\n", i, truncated);
    }
}

0x50 isn't a power of 2, so it has odd prime factors. That makes it fundamentally harder on a binary computer. Quotient and remainder both depend on all the higher bits of the whole integer.

Dario's mod5 idea taking advantage of the 2^n + 1 special case is quite useful, avoiding the full general case of a multiplicative inverse or a shift/add iterative division.

It's still somewhat painful, especially since 6800 (unlike AVR) can only shift by 1. AVR's swap instruction (exchanging nibbles = rotate by 4) is useful here, with compilers making good use of it to shift by 4, for a C version of Dario's code (https://godbolt.org/z/c7qhKx6aY).

AVR is another 8-bit microcontroller, so it's somewhat interesting to see how compilers do things there. It has 32 registers, vs. 6800's two (plus a 16-bit IX, but operations on that are quite limited: http://www.8bit-era.cz/6800.html lists the instruction set). It only has shifts by 1, nothing like AVR's swap that I can see, so shifting by 4 is more expensive. (Shifting by 8 is still free, 16-bit numbers are still stored in 8-bit halves.)

I introduced new uint8_t variables where values were narrow enough for that, helping compilers avoid wasting instructions. (And identifying those spots for a hand-written asm version.) I also rewrote things to potentially do less shifting, especially less full 16-bit shifting, but I think there's more room for such optimizations by hand, e.g. maybe working with shifted values to return a mod5 << 4 directly, instead of making the caller do that.

e.g. (x >> 4) + (x & 0xF) could potentially be (x & 0xf0) + ((uint8_t)x<<4), but that wouldn't make it fit within a byte; there's still be a bit that might extend into the next byte. Perhaps only right shift one or two bit positions, so there's less distance to shift back after using 8-bit subtraction to do the m -= 15 and m -= 5 steps.

Otherwise at least the first of those steps would have to deal with the top of the value extending into another byte. Borrow only propagates from low to high, but you do need to compare correctly so you can't just truncate and discard it; that would be mod 16 not mod 15.

#include <stdint.h>

inline
uint8_t mod15(unsigned short x){
    x = (x >> 8) + (x & 0xFF);     // carry-out can produce a 9-bit result
    uint8_t m = (x >> 4) + (x & 0xF);
#if 0
    do {
         m -= 15; 
    } while((int8_t)m >= 0);
    m += 15;
#else
    if(m >= 15) m -= 15;
    //if(m >= 15) m -= 15; // not needed for partial range
#endif
  // or slower, just let a mod5 loop run potentially more iterations
    return m;
}

inline
uint8_t mod5(unsigned short x){
    uint8_t m = mod15(x);
    //while(!__builtin_sub_overflow(m, 5, &m) ){}
    //m += 5;

    //uint8_t m1 = m - 5;
    //if (m < 5) return m1;
#if 1
    do {  // GCC makes a small loop, clang calls a modulo function :/
         m -= 5;
    } while((int8_t)m >= 0);
    m += 5;
#else
    if(m >= 5) m -= 5;
    if(m >= 5) m -= 5;
#endif
    return m;
}

unsigned short round80(unsigned short x){
    //x >>= 4;
    uint8_t m5 = mod5(x>>4);
    x &= -16;
    x -= m5 << 4;
    //x <<= 4;
    return x;
}

I haven't yet actually tried to write a 6800 version of it; it would very likely need some scratch space, either on the stack with push / pull, or some cheaper to access space somewhere. With only 2 8-bit registers A and B, that's the whole value.

16-bit right shift by 1 can be done with LSR B / ROR A. That does need to happen at some point I think, but perhaps can be avoided as much as possible if it's going to be un-done later.

As already written in other answers, I would use the fact that 80=5*16:

This allows you to round down to the nearest multiple of 80 using the following algorithm (shown as C-like code):

/* Step 1: Clear the lower 4 bits */
X = X & ~0xF;
/* Step 2: Round down the upper N-4 bits to a multiple of 5 */
X -= ((X >> 4) % 5) << 4; 

The first step is a simple AND operation.

The operation (X >> 4) % 5 can be performed using the following pseudo code for a 16-bit number:

# A, H and L are 8-bit registers or memory locations
A = 0
H:L = X
REPEAT 12 TIMES
    A:H:L <<= 1
    A -= 5
    IF A < 0
        A += 5
    END_OF_IF
END_OF_LOOP
# Now A contains (X >> 4) % 5

I didn't work with 6800 code since the early 1990s, so the following code may be wrong:

# RAM locations:
#  [X_low] = Initially holding low 8 bits of the number;
#            finally holding low 8 bits of the result
#  [X_high] = ... high 8 bits ...
#  [TmpH] = Temporary memory;
#           corresponds to "H" in pseudo-code
#  [TmpL] = Temporary memory; ... "L" ...

# Step one: Clear the lower 4 bits
LDAA [X_low]
ANDA #0xF0
STAA [X_low]

# Prepare for step two
# Note: AccA still contains X_low
STAA [TmpL]
LDAA [X_high]
STAA [TmpH]
CLR A
LDAB #12

# The loop
loop:
ASL [TmpL]
ROL [TmpH]
ROL A
SUBA #5
BCC notSmallerThanZero
ADDA #5
notSmallerThanZero:
DEC B
BNE loop

# Now AccA contains (X >> 4) % 5
# Calculate ((X >> 4) % 5) << 4
ASL A
ASL A
ASL A
ASL A

# ... and subtract that value from X
TAB
LDAA [X_low]
SBA
BCC noCarry
DEC [X_high]
noCarry:
STAA [X_low]