nybble-wide integer math

Fork

/* Division functions for an eight-bit framework 
// for testing various arithmetic techniques.
// Written by Joel Matthew Rees
// Copyright 2013, Joel Matthew Rees
// Distribution and use permitted under terms of the GPL v. 3,
// See the included file, LICENSE.TXT,
// or on-line at <http://www.gnu.org/licenses/>. 
*/


#include <stdio.h>
#include <limits.h>


#include "nibBit.h"


/*
01800 USLASH	LDA #17 bit ct
01810 	PSHS A
01820 	LDD 2,U dividend
01830 USLDIV	CMPD ,U divisor
01840 	BHS USLSUB
01850 	ANDCC #.NOT.1
01860 	BRA USLBIT
01870 USLSUB	SUBD ,U
01880 	ORCC #1 quotient,
01890 USLBIT	ROL 5,U save it
01900 	ROL 4,U
01910 	DEC ,S more bits?
01920 	BEQ USLR
01930 	ROLB remainder
01940 	ROLA
01950 	BCC USLDIV
01960 	BRA USLSUB
01970 USLR	LEAS 1,S
01980 	LEAU 2,U
01990 	LDX 2,U
02000 	STD 2,U
02010 	STX ,U
02020 	NEXT
02030 *
*/
/* Push order: dividend-lsbyte dividend-msbyte divisor 
// return order: remainder quotient
// (quotient on top-of-stack -- at low address)
// The high byte of the dividend is a trick to avoid shifting.
// It gets partially discarded, how much depends on the divisor.
*/
void nibBUDiv( void )
{
   unsigned count = BYTEBITS + 1; /* byte wide, so we aren't here all day. */
   uchar_t divisor = ( * mySP++ );
   uchar_t dividendHi = mySP[ 0 ];  /* Thrown away, in part. */
   uchar_t dividendLo = mySP[ 1 ]; 
   uchar_t quotient = 0;
   uchar_t carry = 0;
   for ( ;; )
   {  
      if ( carry || ( dividendHi >= divisor ) ) /* Two's complement only */
      {
         quotient |= 1;
         dividendHi -= divisor;
      }
      if ( --count <= 0 )
      {  break;
      }
      quotient <<= 1;
      carry = dividendHi & BYTEHIBIT;
      dividendHi <<= 1;
      if ( ( dividendLo & BYTEHIBIT ) != 0 )
      {  dividendHi |= 1;
      }
      dividendLo <<= 1;
   }
   mySP[ 0 ] = quotient;
   mySP[ 1 ] = dividendHi; /* At this point, the remainder. */
}
/* When done correctly, catching the carry, etc., 
// divide-by-shift is a covering complement to multiply-by-shift.
//
// That is, the above 16 bit dividend, 8 bit divisor unsigned divide
// covers all the possible results of an 8 bit by 8 bit unsigned multiply.
// (It hits and misses n>8 quotients and m<8 divisor cases.)
//
// If you have a hardware divide equivalent to the above, 
// you can use it (at assembler level) to implement U/, 
// and build M/MOD from U/.
// In other words, an unsigned divide with 
// double word dividend, word divisor, 
// and word quotient and remainder
// can be used to synthesize a full double word result
// using half-word shifting.
// 
// 
// To fully cover all double word divisions and word bit divisors, 
// one might prime the loop with a zero word 
// and shift-divide three words of dividend by double word bit width.
*/


/* Push order: dividend-lsbyte dividend-msbyte divisor 
// return order: remainder quotient
// test return order: remainder-lsbyte remainder-msbyte quotient
// (quotient on top-of-stack -- at low address)
// The high byte of the dividend is a trick to avoid shifting.
// It gets partially discarded, how much depends on the divisor.
*/
void nibUDiv( void )
{
   uchar_t divisor = mySP[ 0 ];
   uchar_t dividendHi = mySP[ 1 ];
   uchar_t dividendLo = mySP[ 2 ];

/*
printf( "start dividendHi: %d, dividendLo: %d, divisor: %d\n", 
        dividendHi, dividendLo, divisor );
*/
   if ( dividendHi == 0 )
   {   /* Short circuit */
      mySP[ 2 ] = dividendLo % divisor;
      mySP[ 1 ] = dividendLo / divisor;
#if defined TESTUDIVHIGHWORD
      mySP[ 0 ] = 0;
/*
printf( "native qHi: %d, qLo: %d, rem: %d\n", 
        mySP[ 0 ], mySP[ 1 ], mySP[ 2 ] );
*/
#else /* !defined TESTUDIVHIGHWORD */
      ++mySP;
#endif /* defined TESTUDIVHIGHWORD */

      return; 
   }
   if ( NIBHI( divisor ) == 0 )
   {  /* This covers the full range of dividends vs. nibble-only divisors. */
      uchar_t quotientHi = dividendHi / divisor; /* throwaway */
      uchar_t carry = dividendHi % divisor; /* 0 .. 0x0f */
      uchar_t dividendMidHi = NIBLOUP( carry ) | NIBHIDOWN ( dividendLo );
      uchar_t quotientMidLo = dividendMidHi / divisor;
      uchar_t quotientLo;
/*
printf( "qHi: %d, dMHi: %d, qMLo: %d, carry: %d\n", 
        quotientHi, dividendMidHi, quotientMidLo, carry );
*/
      carry = dividendMidHi % divisor;
      dividendLo &= NIBLOMASK;
      dividendLo |= NIBLOUP( carry );
      quotientLo = dividendLo / divisor;
/*
printf( "qLo: %d, dLo: %d, carry: %d\n", 
        quotientLo, dividendLo, carry );
*/
      mySP[ 2 ] = dividendLo % divisor;
      mySP[ 1 ] = NIBLOUP( quotientMidLo ) | quotientLo;
#if defined TESTUDIVHIGHWORD
      mySP[ 0 ] = quotientHi;
/*
printf( "nibble qHi: %d, qLo: %d, rem: %d\n", 
        mySP[ 0 ], mySP[ 1 ], mySP[ 2 ] );
*/
#else /* !defined TESTUDIVHIGHWORD */
      ++mySP;
#endif /* defined TESTUDIVHIGHWORD */
      return;
   }
   else
   {  /* Divisor > 0x0f */
      unsigned count = BYTEBITS * 2 + 1; 
      uchar_t quotientHi = 0;
      uchar_t quotientLo = 0;
      uchar_t carry = 0;
      uchar_t dividendLead = 0;
      for ( ;; )
      {  
         if ( carry || ( dividendLead >= divisor ) ) /* 2's complement only */
         {
            quotientLo |= 1;
            dividendLead -= divisor;
         }
         if ( --count <= 0 )
         {  break;
         }
         quotientHi <<= 1;
         if ( ( quotientLo & BYTEHIBIT ) != 0 )
         {  quotientHi |= 1;
         }
         quotientLo <<= 1;
         carry = dividendLead & BYTEHIBIT;
         dividendLead <<= 1;
         if ( ( dividendHi & BYTEHIBIT ) != 0 )
         {  dividendLead |= 1;
         }
         dividendHi <<= 1;
         if ( ( dividendLo & BYTEHIBIT ) != 0 )
         {  dividendHi |= 1;
         }
         dividendLo <<= 1;
      }
      mySP[ 1 ] = quotientLo;
      mySP[ 2 ] = dividendLead; /* At this point, the remainder. */

#if defined TESTUDIVHIGHWORD
      mySP[ 0 ] = quotientHi;
/*
printf( "nibble qHi: %d, qLo: %d, rem: %d\n", 
        mySP[ 0 ], mySP[ 1 ], mySP[ 2 ] );
*/
#else /* !defined TESTUDIVHIGHWORD */
      ++mySP;
#endif /* defined TESTUDIVHIGHWORD */

      return;
   }
}