Page 1 of 2
Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 5:09 am
by 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
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 6:59 am
by 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 ...
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 9:03 am
by 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
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 9:15 am
by 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
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 10:09 am
by 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.
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 4:03 pm
by 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.
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 4:56 pm
by rwiker
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!
Re: Signed 16-bit right shift question with -1 shift check
Posted: Sun Oct 07, 2018 11:18 pm
by 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
Re: Signed 16-bit right shift question with -1 shift check
Posted: Mon Oct 08, 2018 12:06 am
by 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.
Re: Signed 16-bit right shift question with -1 shift check
Posted: Mon Oct 08, 2018 1:02 am
by 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:
}
Re: Signed 16-bit right shift question with -1 shift check
Posted: Mon Oct 08, 2018 5:18 am
by paul_nicholls
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!
Re: Signed 16-bit right shift question with -1 shift check
Posted: Mon Oct 08, 2018 9:11 pm
by JimBoyd
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
}
Re: Signed 16-bit right shift question with -1 shift check
Posted: Tue Oct 09, 2018 2:42 am
by dmsc
Hi!
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
}
Re: Signed 16-bit right shift question with -1 shift check
Posted: Tue Oct 09, 2018 4:30 am
by 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 ...
Re: Signed 16-bit right shift question with -1 shift check
Posted: Tue Oct 09, 2018 8:26 am
by BitWise
Nice work