Signed 16-bit right shift question with -1 shift check

[paul_nicholls]

Hi all,
I have the following code which right shifts by 1 bit a signed 16-bit number:

Code: Select all

.macro div2_16bit(address) {
  lda address + 1      // load the msb
  asl                  // copy the sign bit into c
  ror address + 1      // and back into the msb
  ror address + 0      // rotate the lsb as normal
}

This works well until I try to shift a number with the value -1 as I still get -1...

My question is, is there a fast way to test to see if I have tried to "divide by 2" the value "-1" and if so, set the value to 0?

cheers,
Paul

[barrym95838]

Simple integer division like you're describing can often result in silent truncation toward negative infinity. In your case the carry flag on exit will tell you if truncation occurred, and you can use it with the sign of the argument to "round-toward-zero", assuming that's the behavior you seek. If you just want to force -1/2 to zero as a special case, you can try the following:

Code: Select all

.macro div2_16bit(address) {
  ldx address + 1      // load the msb
  cpx #$80             // copy the sign bit into c
  ror address + 1      // and back into the msb
  ror address + 0      // rotate the lsb as normal
  inx
  bne done             // see if orig. argument was -1,
  ldx address + 0
  inx
  bne done
  stx address + 1      // ... and force result to 0 if it was
  stx address + 0
done:
}

Wow, there must be a more efficient way than that, but it's past my bed time again and my fuel gauge is on "E", so I'll leave you in the capable hands of the other members ...

[paul_nicholls]

Thanks Mike B

That seems to work ok if the value is -1 before the macro, but if the value is -2 before the macro then the result becomes 0 right away instead of -1 as I would have expected.

cheers,
Paul

[paul_nicholls]

I had a fiddle (not a short as your version) and got something to work:

Code: Select all

.macro div2_16bit(address) {
  // is the value -1 at the start?
  lda address + 1
  cmp #255
  bne divBy2
  lda address + 0
  cmp #255
  bne divBy2

  // yes, so set to zero and exit
  lda #0
  sta address + 1
  sta address + 0
  jmp done

divBy2:
  lda address + 1      // load the msb
  asl                  // copy the sign bit into c
  ror address + 1      // and back into the msb
  ror address + 0      // rotate the lsb as normal
done:
}

Something shorter if possible would be nice

[Martin A]

How about

Code: Select all

lda address + 1
and address + 0
cmp #255
beq setzero
divby2:
…
setzero:
...

To check for -1, it saves bytes at the expense of the early exit if the first test fails.

Re ordering the code to branch on -1 would save 1 cycle in the majority case.

[barrym95838]

Oh, yeah, a bcc done before the first inx would probably correct the bug in my original attempt, at the expense of two more bytes. Here's a fresh attempt that seems to be a bit more (space) efficient (thanks to Martin A for the seed of the idea):

Code: Select all

.macro div2_16bit(address) {
  lda address + 1      // load the msb
  cmp #$80             // copy the sign bit into c
  ror address + 1      // rotate sign into the msb
  and address + 0      // check for special case -1
  ror address + 0      // rotate the lsb as normal
  eor #$ff             // complete the -1 detection
  bne done
  sta address + 1      // force result to 0 only if
  sta address + 0      // original input was -1
done:
}

I always default to optimizing for size rather than speed.

[rwiker]

barrym95838 wrote:

Oh, yeah, a bcc done before the first inx would probably correct the bug in my original attempt, at the expense of two more bytes. Here's a fresh attempt that seems to be a bit more (space) efficient (thanks to Martin A for the seed of the idea):

Code: Select all

.macro div2_16bit(address) {
  lda address + 1      // load the msb
  cmp #$80             // copy the sign bit into c
  ror address + 1      // rotate sign into the msb
  and address + 0      // check for special case -1
  ror address + 0      // rotate the lsb as normal
  eor #$ff             // complete the -1 detection
  bne done
  sta address + 1      // force result to 0 only if
  sta address + 0      // original input was -1
done:
}

I always default to optimizing for size rather than speed.

Neat!

[JimBoyd]

As was already suggested, you can test for -1 before the division.
My question is, does the -1 result cause a problem with your program? In other words, does your program require symetrical integer division or can you use floored integer division?
With floored integer division, if the real result of the division lies between two consecutive integers, the lower value is returned. Since -1/2 is between 0 and -1, -1 is the correct result of -1 divided by 2.

Cheers,
Jim

[JimBoyd]

If you need symetrical division ( without the remainder ), this code should do it.

Code: Select all

.macro div2_16bit(address) {
  LDA address + 1      // load the msb
  ASL                  // copy the sign bit into c
  ROR address + 1      // and back into the msb
  ROR address + 0      // rotate the lsb as normal
  LDA address + 1      // load the msb
  BPL skip             // if negative
  LDA address + 0      // add the carry
  ADC #$0              // back to the result
  STA address + 0      // to force symetric division
  LDA address + 1
  ADC #$0
  STA address + 1
skip:
}

I am away from my desktop at the moment, which has the c64 simulator, so I can't fully test this code. I did a brief check on easy 6502.

[barrym95838]

I like Jim's symmetrical routine better than just special-casing -1/2, but I think I can make it shorter and possibly even faster if we don't mind getting register x involved (untested):

Code: Select all

.macro div2_16bit(address) {
  lda address + 1
  cmp #$80
  ror                  // load the msb
  ror address + 0      // rotate the lsb as normal
  tax                  // check sign
  bpl done
  bcc done
  inc address + 0      // adjust toward 0 only if
  bne done             //   # < 0 and remainder = 1
  inx
done:
  stx address + 1      // store msb
}

Here's one that's a little bigger and slower, but doesn't mess with a or x (also untested):

Code: Select all

.macro div2_16bit(address) {
  clc
  bit address + 1      // check and preserve the
  bpl positive         //   sign in the carry
  sec
positive:
  ror address + 1      // arithmetic shift the msb 
  ror address + 0      // rotate the lsb as normal
  bcc done
  bit address + 1
  bpl done
  inc address + 0      // adjust toward 0 only if
  bne done             //   # < 0 and remainder = 1
  inc address + 1
done:
}

[paul_nicholls]

JimBoyd wrote:

As was already suggested, you can test for -1 before the division.
My question is, does the -1 result cause a problem with your program? In other words, does your program require symetrical integer division or can you use floored integer division?
With floored integer division, if the real result of the division lies between two consecutive integers, the lower value is returned. Since -1/2 is between 0 and -1, -1 is the correct result of -1 divided by 2.

Cheers,
Jim

Hmm...good question @JimBoyd...I might have been hasty as I do want floored division...I ultimately want to convert a 16-bit x value to its column value using the equivalent of column = floor(x/8.0).

I thought I could call my 16-bit signed shift routine 3 times to do this.

Thanks for all the great answers and help all!

[JimBoyd]

barrym95838 wrote:

I like Jim's symmetrical routine better than just special-casing -1/2, but I think I can make it shorter and possibly even faster if we don't mind getting register x involved (untested):

I like the short version, however if the x register needs preserved because it is used for something like a data stack pointer , then the y register could be used in place of the x register.

Code: Select all

.macro div2_16bit(address) {
  lda address + 1
  cmp #$80
  ror                  // load the msb
  ror address + 0      // rotate the lsb as normal
  tay                  // check sign
  bpl done
  bcc done
  inc address + 0      // adjust toward 0 only if
  bne done             //   # < 0 and remainder = 1
  iny
done:
  sty address + 1      // store msb
}

[dmsc]

Hi!

JimBoyd wrote:

barrym95838 wrote:

I like Jim's symmetrical routine better than just special-casing -1/2, but I think I can make it shorter and possibly even faster if we don't mind getting register x involved (untested):

I like the short version, however if the x register needs preserved because it is used for something like a data stack pointer , then the y register could be used in place of the x register.

Code: Select all

.macro div2_16bit(address) {
  lda address + 1
  cmp #$80
  ror                  // load the msb
  ror address + 0      // rotate the lsb as normal
  tay                  // check sign
  bpl done
  bcc done
  inc address + 0      // adjust toward 0 only if
  bne done             //   # < 0 and remainder = 1
  iny
done:
  sty address + 1      // store msb
}

If you add 1 before shifting, it is 2 bytes shorter:

Code: Select all

.macro div2_16bit(address) {
  ldy address + 1
  cpy #$80
  bcc ok
  inc address +0
  bne ok
  iny
ok:
  tya
  ror
  ror address + 0
  sta address + 1
}

[barrym95838]

Ah, well done, dmsc! You saved us a bpl, and it looks like you trimmed it about as lean as it's gonna get (heck, you even got rid of those flabby comments) ... unless someone like dclxvi or bogax flops a little gem onto the table from low Earth orbit ...

[BitWise]

Nice work