c_cpp/etc/calc/jump.h

   1 /*
   2  * jump - trivial prime jump table
   3  *
   4  * Copyright (C) 1999-2007  Landon Curt Noll
   5  *
   6  * Calc is open software; you can redistribute it and/or modify it under
   7  * the terms of the version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * Calc is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  13  * Public License for more details.
  14  *
  15  * A copy of version 2.1 of the GNU Lesser General Public License is
  16  * distributed with calc under the filename COPYING-LGPL.  You should have
  17  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  18  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  *
  20  * @(#) $Revision: 30.1 $
  21  * @(#) $Id: jump.h,v 30.1 2007/03/16 11:09:46 chongo Exp $
  22  * @(#) $Source: /usr/local/src/bin/calc/RCS/jump.h,v $
  23  *
  24  * Under source code control:   1994/06/29 04:03:55
  25  * File existed as early as:    1994
  26  *
  27  * chongo <was here> /\oo/\     http://www.isthe.com/chongo/
  28  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  29  */
  30
  31 /*
  32  * If x is divisible by a trivial prime (2,3,5,7,11), then:
  33  *
  34  *              x + jmpindx[ (x>>1)%JMPMOD ]
  35  *
  36  * is the value of the smallest value > x that is not divisible by a
  37  * trivial prime.  JMPMOD is the product of the odd trivial primes.
  38  *
  39  * This table is useful for skipping values that are obviously not prime
  40  * by skipping values that are a multiple of trivial prime.
  41  *
  42  * If x is not divisible by a trivial prime, then:
  43  *
  44  *              x + jmp[ -jmpindx[(x>>1)%JMPMOD] ]
  45  *
  46  * is the value of the smallest value > x that is not divisible by a
  47  * trivial prime.
  48  *
  49  * If jmpindx[y] > 0 (y = x mod JMPMOD*2), then it refers to an 'x' that
  50  * is divisible by a trivial prime and jmpindx[y] is the offset to the next
  51  * value that is not divisible.
  52  *
  53  * If jmpindx[y] <= 0, then 'x' is not divisible by a trivial prime and
  54  * the negative of jmpindx[y] is the index into the jmp[] table.  We use
  55  * successive values from jmp[] (wrapping around to the beginning when
  56  * we move off the end of jmp[]) to move to higher and higher values
  57  * that are not divisible by trivial primes.
  58  *
  59  * Instead of testing successive odd values, this system allows us to
  60  * skip odd values divisible by trivial primes.  This is process on the
  61  * average reduces the values we need to test by a factor of at least 2.4.
  62  */
  63
  64
  65 #if !defined(__JUMP_H__)
  66 #define __JUMP_H__
  67
  68
  69 #if defined(CALC_SRC)   /* if we are building from the calc source tree */
  70 # include "have_const.h"
  71 # include "decl.h"
  72 #else
  73 # include <calc/have_const.h>
  74 # include <calc/decl.h>
  75 #endif
  76
  77
  78 /*
  79  * trivial prime CONSTants
  80  */
  81 #define JMPMOD (3*5*7*11)       /* product of odd trivial primes */
  82 #define JMPSIZE (2*4*6*10)      /* ints mod JMPMOD not div by trivial primes */
  83 #define JPRIME (prime+4)        /* pointer to first non-trivial prime */
  84
  85 /* given x, return the index within jmpindx that applies */
  86 #define jmpmod(x) (((x)>>1)%JMPMOD)
  87
  88 /* jmpindx table value */
  89 #define jmpindxval(x) (jmpindx[jmpmod(x)])
  90
  91 /* return the smallest value >= x not divisible by a trivial prime */
  92 #define firstjmp(x,tmp) ((tmp) = jmpindxval(x), ((tmp) > 0) ? ((x)+(tmp)) : (x))
  93
  94 /* given x not divisible by a trivial prime, return jmp[] index */
  95 #define jmpptr(x) (-jmpindxval(x))
  96
  97 /* given a jmp pointer, return current jump increment and bump the pointer */
  98 #define nxtjmp(p) ( *( ((p)<lastjmp) ? ((p)++) : (((p)=jmp),lastjmp) ) )
  99
 100 /* given a jmp pointer, return dec pointer and return previous jump increment */
 101 #define prevjmp(p) ( *( ((p)>jmp) ? (--(p)) : ((p)=lastjmp) ) )
 102
 103 /*
 104  * external jump tables
 105  */
 106 EXTERN CONST short jmpindx[];
 107 EXTERN CONST unsigned char jmp[];
 108 EXTERN CONST unsigned char *CONST lastjmp;
 109
 110 #endif /* !__JUMP_H__ */