[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

bit-extract using mpz

From: Kevin Ryde
Subject: bit-extract using mpz
Date: Sat, 15 Nov 2003 08:21:54 +1000
User-agent: Gnus/5.1003 (Gnus v5.10.3) Emacs/21.3 (gnu/linux)

        * numbers.c (scm_bit_extract): Use mpz functions, rearrange inum case
        to share some shifting.

The existing bit-operations.test does a good job on this, I couldn't
spot further cases that wanted exercising.

New code, for ease of contemplation:

#define MIN(x,y)  ((x) < (y) ? (x) : (y))

SCM_DEFINE (scm_bit_extract, "bit-extract", 3, 0, 0,
            (SCM n, SCM start, SCM end),
            "Return the integer composed of the @var{start} (inclusive)\n"
            "through @var{end} (exclusive) bits of @var{n}.  The\n"
            "@var{start}th bit becomes the 0-th bit in the result.\n"
            "(number->string (bit-extract #b1101101010 0 4) 2)\n"
            "   @result{} \"1010\"\n"
            "(number->string (bit-extract #b1101101010 4 9) 2)\n"
            "   @result{} \"10110\"\n"
            "@end lisp")
#define FUNC_NAME s_scm_bit_extract
  unsigned long int istart, iend, bits;
  SCM_VALIDATE_INUM_MIN_COPY (2, start,0, istart);
  SCM_VALIDATE_INUM_MIN_COPY (3, end, 0, iend);
  SCM_ASSERT_RANGE (3, end, (iend >= istart));

  /* how many bits to keep */
  bits = iend - istart;

  if (SCM_INUMP (n))
      long int in = SCM_INUM (n);

      /* When istart>=SCM_I_FIXNUM_BIT we can just limit the shift to
         SCM_I_FIXNUM_BIT-1 to get either 0 or -1 per the sign of "in".
         FIXME: This shift relies on signed right shifts being arithmetic,
         which is not guaranteed by C99. */
      in >>= MIN (istart, SCM_I_FIXNUM_BIT-1);

      if (in < 0 && bits >= SCM_I_FIXNUM_BIT)
          /* Since we emulate two's complement encoded numbers, this
           * special case requires us to produce a result that has
           * more bits than can be stored in a fixnum.
          SCM result = scm_i_long2big (in);
          mpz_fdiv_r_2exp (SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (result),
          return result;

      /* mask down to requisite bits */
      bits = MIN (bits, SCM_I_FIXNUM_BIT);
      return SCM_MAKINUM (in & ((1L << bits) - 1));
  else if (SCM_BIGP (n))
      SCM result;
      if (bits == 1)
          result = SCM_MAKINUM (mpz_tstbit (SCM_I_BIG_MPZ (n), istart));
          /* ENHANCE-ME: It'd be nice not to allocate a new bignum when
             bits<SCM_I_FIXNUM_BIT.  Would want some help from GMP to get
             such bits into a ulong.  */
          result = scm_i_mkbig ();
          mpz_fdiv_q_2exp (SCM_I_BIG_MPZ(result), SCM_I_BIG_MPZ(n), istart);
          mpz_fdiv_r_2exp (SCM_I_BIG_MPZ(result), SCM_I_BIG_MPZ(result), bits);
          result = scm_i_normbig (result);
      scm_remember_upto_here_1 (n);
      return result;
#undef FUNC_NAME

Attachment: numbers.c.bit-extract.diff
Description: Text document

reply via email to

[Prev in Thread] Current Thread [Next in Thread]