6502.org Forum Projects Code Documents Tools Forum
It is currently Thu Apr 25, 2024 5:14 pm

View unanswered posts | View active topics


Board index » 6502.org Users Forum » Programming

All times are UTC




Post new topic Reply to topic  Page 1 of 2
  [ 20 posts ]  Go to page 1, 2  Next
  Previous topic | Next topic 
Author Message
paul_nicholls
PostPosted: Sun Oct 07, 2018 5:09 am 
Offline

Joined: Wed Jan 19, 2011 10:20 pm
Posts: 41
Hi all,
I have the following code which right shifts by 1 bit a signed 16-bit number:

Code:
.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

_________________
"The plastic veneer of civilization is easily melted in the heat of the moment" - Paul Nicholls
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Sun Oct 07, 2018 6:59 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1926
Location: Sacramento, CA, USA
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:
.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 ...

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
Top
 Profile  
Reply with quote  
paul_nicholls
PostPosted: Sun Oct 07, 2018 9:03 am 
Offline

Joined: Wed Jan 19, 2011 10:20 pm
Posts: 41
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

_________________
"The plastic veneer of civilization is easily melted in the heat of the moment" - Paul Nicholls
Top
 Profile  
Reply with quote  
paul_nicholls
PostPosted: Sun Oct 07, 2018 9:15 am 
Offline

Joined: Wed Jan 19, 2011 10:20 pm
Posts: 41
I had a fiddle (not a short as your version) and got something to work:

Code:
.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:
}


Image

Something shorter if possible would be nice :D

_________________
"The plastic veneer of civilization is easily melted in the heat of the moment" - Paul Nicholls
Top
 Profile  
Reply with quote  
Martin A
PostPosted: Sun Oct 07, 2018 10:09 am 
Offline

Joined: Sat Jan 02, 2016 10:22 am
Posts: 197
How about

Code:
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.
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Sun Oct 07, 2018 4:03 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1926
Location: Sacramento, CA, USA
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:
.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.

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
Top
 Profile  
Reply with quote  
rwiker
PostPosted: Sun Oct 07, 2018 4:56 pm 
Offline

Joined: Thu Mar 03, 2011 5:56 pm
Posts: 277
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:
.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!
Top
 Profile  
Reply with quote  
JimBoyd
PostPosted: Sun Oct 07, 2018 11:18 pm 
Offline

Joined: Fri May 05, 2017 9:27 pm
Posts: 851
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
Top
 Profile  
Reply with quote  
JimBoyd
PostPosted: Mon Oct 08, 2018 12:06 am 
Offline

Joined: Fri May 05, 2017 9:27 pm
Posts: 851
If you need symetrical division ( without the remainder ), this code should do it.
Code:
.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.
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Mon Oct 08, 2018 1:02 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1926
Location: Sacramento, CA, USA
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:
.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:
.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:
}

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
Top
 Profile  
Reply with quote  
paul_nicholls
PostPosted: Mon Oct 08, 2018 5:18 am 
Offline

Joined: Wed Jan 19, 2011 10:20 pm
Posts: 41
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! :)

_________________
"The plastic veneer of civilization is easily melted in the heat of the moment" - Paul Nicholls
Top
 Profile  
Reply with quote  
JimBoyd
PostPosted: Mon Oct 08, 2018 9:11 pm 
Offline

Joined: Fri May 05, 2017 9:27 pm
Posts: 851
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 :wink: , then the y register could be used in place of the x register.
Code:
.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
}
Top
 Profile  
Reply with quote  
dmsc
PostPosted: Tue Oct 09, 2018 2:42 am 
Offline

Joined: Mon Sep 17, 2018 2:39 am
Posts: 132
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 :wink: , then the y register could be used in place of the x register.
Code:
.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:
.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
}
Top
 Profile  
Reply with quote  
barrym95838
PostPosted: Tue Oct 09, 2018 4:30 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1926
Location: Sacramento, CA, USA
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 ...

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)
Top
 Profile  
Reply with quote  
BitWise
PostPosted: Tue Oct 09, 2018 8:26 am 
Offline
User avatar

Joined: Tue Mar 02, 2004 8:55 am
Posts: 996
Location: Berkshire, UK
Nice work

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 2
  [ 20 posts ]  Go to page 1, 2  Next

Board index » 6502.org Users Forum » Programming

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
6502.org is an ongoing project by Mike Naberezny and contributors.