Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.postscript > #1135

Re: Calculate a 16-bit Carry Flag?

Show all headers | View raw

Robert Bonomi wrote:

> In article <k9bbcb$l24$1@dont-email.me>,
> luser.droog <luser.droog@gmail.com> wrote:
>>Robert Bonomi wrote:
>>
>>> In article <k9a31h$ngc$1@dont-email.me>,
>>> luser.droog <luser.droog@gmail.com> wrote:
>>>>I'm debugging my 8086 emulator
>>>>http://codegolf.stackexchange.com/questions/4732/emulate-an-intel-8086-cpu/9065#9065
>>>>
>>>>And I'm hung up on the arithmetic. How do you tell if a 16bit addition
>>>>yield a Carry using postscript's 32-bit (PLRM stnd) integers. Since it's
>>>>all 2's complement, I figured I could just sign-extend all the inputs,
>>>>call the ps math op (`add`, `sub`), and then check the bits.
>>> 
>>> First, implement 'subtract' as 'complement and add'
>>> 
>>> Then:
>>>   *IF* bit {7 15} of the two operands are different you can't have a
>>>   Carry. If they're the same, do the addition, and if bit {7 15} of the
>>>   result is different from operands, overflow occurred
>>
>>Awesome, thanks. So, I shouldn't be sign-extending everything willy-nilly,
>>right? Just treat them as unsigned values since they're all in the
>>positive
>>range of a 32bit signed int?  And by implementing subtract as you say, I
>>only have to do the carry nonsense once.
>>
>>When you say 'overflow', you mean what I mean by 'carry', right? Cause
>>I've got a Carry Flag and an Overflow Flag, and for unsigned overflow,
>>I've got to XOR({7 15},{8 16}). unless I'm mistaken.
>>
> define what *you* mean by 'carry' and 'overflow' :)

Touché.

> from my _distant_ memories, overflow is set on mul/div -- you can't get
> meaningful (even partial) results there.
> 'carry' is set for add/sub  -- only one excess/'lost' bit is possible,
> and you do multiple-precision is done by adding the 'carry' bit as a LSB
> to the 'next more significant' chunk of th operand.
> 
> *dim* recollection of implementation details:
>  a) 'carry' set on =signed= result that carries into sign bit (only).
>     Or unsigned carry into next higher bit.
>  b) 'overflow' set if anything propagates -past- the carry position
>  c) 'overflow' set implies 'carry' set.
> 
> Aside -- beware of gotcha on 'complement and add'. can't complement a
> 'maximum negative' operand.  If 1st operand not 'maximum negative', then
> complement it, else if 2nd operand not 'maximum negative', then complement
> it, else (both are 'maximum negative'), SHORTCUT: result is =zero=.
> 
> Trivia, For a number of years I used a (then supercomputer-class) machine
> that "couldn't add" -- literal truth, it did addition by 'complement and
> subtract'.  at a high level, it was a wonderfully simple (read 'elegant')
> design; the closer to the hardware you got, the _weirder_ it was. Weird,
> but in a wonderful way.  :)

Alright, following this led me to write 

/SUB{D{exch}repeat {{negb ADDB}{negw ADDW}}W get exec}def

/ADDB{ 2 copy signb exch signb ne {
    add /CF 0 def /OF 0 def
}{
    dup signb 3 1 roll % signy x y
    add
    dup signb 3 2 roll % sum signsum signy
    eq {
        /CF 0 def
    }{
        /CF 1 def
    } ifelse
    dup 16#100 and 0 ne {
        /OF 1 def
    }{
        /OF 0 def
    } ifelse
} def

/ADDW { 2 copy 2{ -15 bitshift 1 and exch}repeat ne {
    add /CF 0 def /OF 0 def
}{
    dup -15 bitshift 1 and 3 1 roll
    add dup -15 bitshift 3 2 roll eq {
        /CF 0 def }{ /CF 1 def } ifelse
    dup -16 bitshift 1 and /OF exch def
} def

And that just seems ugly and unmanageable.
So I went back to basics with

/adder { {c y x}{exch def}forall
    x c and y c and x y and or or % Carry
    dup 1 xor x y c and and or % Carry 1-Carry
    x y c or or and % Carry Sum
} def

/addb { {b a}{exch def}forall
    a 1 shiftmask b 1 shiftmask % a' a0 b' b0
    exch 3 1 roll % a' b' a0 b0
    0
    8 { % a' b' a0 b0 c
        adder % a' b' c s
        4 1 roll % s0 a' b' c0
    } repeat % s0 s1 s2 .. s7 c7
    /CF exch def
    7 { 1 bitshift or } repeat
} def

But that's just crazy, right?

So I peeked at the C solution and found:

 33 void set_flag_add_byte( cpu_state_ptr cpu, uint8_t v1, uint8_t v2 )
 34 {
 35         uint16_t dst = (uint16_t)v1 + (uint16_t)v2;
 36
 37         set_psz_flags_byte( cpu, v1 + v2 );
 38
 39         cpu->flags.bit.CF = ( ( dst & 0xff00) != 0 );
 40         cpu->flags.bit.OF = ( ( dst ^ v1 ) & ( dst ^ v2 ) & 0x80 ) != 0;
 41         cpu->flags.bit.AF = ( ( v1 ^ v2 ^ dst ) & 0x10 ) != 0;
 42 }
 43
 44 void set_flag_add_word( cpu_state_ptr cpu, uint16_t v1, uint16_t v2 )
 45 {
 46         uint32_t dst = (uint32_t)v1 + (uint32_t)v2;
 47
 48         set_psz_flags_word( cpu, v1 + v2 );
 49
 50         cpu->flags.bit.CF = ( ( dst & 0xffff0000 ) != 0 );
 51         cpu->flags.bit.OF = ( ( ( dst ^ v1 ) & ( dst ^ v2 ) &
0x8000 ) != 0 );
 52         cpu->flags.bit.AF = ( ( ( v1 ^ v2 ^ dst ) & 0x10 ) != 0 );
 53 }
 54
 55 void set_flag_sub_byte( cpu_state_ptr cpu, uint8_t v1, uint8_t v2 )
 56 {
 57         uint16_t dst = (uint16_t)v1 - (uint16_t)v2;
 58
 59         set_psz_flags_byte(cpu, v1 - v2 );
 60
 61         cpu->flags.bit.CF = ( ( dst & 0xff00) != 0 );
 62         cpu->flags.bit.OF = ( ( ( v1 ^ dst ) & ( v1 ^ v2 ) & 0x80 ) !=
0 );
 63         cpu->flags.bit.AF = ( ( ( v1 ^ v2 ^ dst ) & 0x10 ) != 0 );
 64 }
 65
http://codegolf.stackexchange.com/a/6514/2381

Now that's something I can steal!

    

Back to comp.lang.postscript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Calculate a 16-bit Carry Flag? "luser.droog" <luser.droog@gmail.com> - 2012-11-30 04:50 -0600
  Re: Calculate a 16-bit Carry Flag? bonomi@host122.r-bonomi.com (Robert Bonomi) - 2012-11-30 11:03 -0600
    Re: Calculate a 16-bit Carry Flag? "luser.droog" <luser.droog@gmail.com> - 2012-11-30 16:18 -0600
      Re: Calculate a 16-bit Carry Flag? bonomi@host122.r-bonomi.com (Robert Bonomi) - 2012-12-02 00:12 -0600
        Re: Calculate a 16-bit Carry Flag? "luser.droog" <luser.droog@gmail.com> - 2012-12-03 00:06 -0600
        Re: Calculate a 16-bit Carry Flag? vojta@math.berkeley.edu (Paul Vojta) - 2012-12-05 02:57 +0000
          Re: Calculate a 16-bit Carry Flag? "luser.droog" <luser.droog@gmail.com> - 2012-12-05 23:34 -0600
            Re: Calculate a 16-bit Carry Flag? Bogus@Embarq.com (Steve) - 2012-12-07 15:59 +0000

csiph-web