git.sur5r.net Git - cc65/blob - src/common/alignment.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                alignment.c                                */
   4 /*                                                                           */
   5 /*                             Address aligment                              */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2011,      Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                70794 Filderstadt                                          */
  12 /* EMail:         uz@cc65.org                                                */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 /* common */
  37 #include "alignment.h"
  38 #include "check.h"
  39
  40
  41
  42 /*****************************************************************************/
  43 /*                                   Data                                    */
  44 /*****************************************************************************/
  45
  46
  47
  48 /* To factorize an alignment, we will use the following prime table. It lists
  49  * all primes up to 256, which means we're able to factorize alignments up to
  50  * 0x10000. This is checked in the code.
  51  */
  52 static const unsigned char Primes[] = {
  53       2,   3,   5,   7,  11,  13,  17,  19,  23,  29,
  54      31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
  55      73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
  56     127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  57     179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  58     233, 239, 241, 251
  59 };
  60 #define PRIME_COUNT     (sizeof (Primes) / sizeof (Primes[0]))
  61 #define LAST_PRIME      ((unsigned long)Primes[PRIME_COUNT-1])
  62 #define FAC_MAX         0x10000UL
  63
  64
  65
  66 /* A number together with its prime factors */
  67 typedef struct FactorizedNumber FactorizedNumber;
  68 struct FactorizedNumber {
  69     unsigned long       Value;                  /* The actual number */
  70     unsigned long       Remainder;              /* Remaining prime */
  71     unsigned char       Powers[PRIME_COUNT];    /* Powers of the factors */
  72 };
  73
  74
  75
  76 /*****************************************************************************/
  77 /*                                   Code                                    */
  78 /*****************************************************************************/
  79
  80
  81
  82 static void Initialize (FactorizedNumber* F, unsigned long Value)
  83 /* Initialize a FactorizedNumber structure */
  84 {
  85     unsigned I;
  86
  87     F->Value = Value;
  88     F->Remainder = 1;
  89     for (I = 0; I < PRIME_COUNT; ++I) {
  90         F->Powers[I] = 0;
  91     }
  92 }
  93
  94
  95
  96 static void Factorize (unsigned long Value, FactorizedNumber* F)
  97 /* Factorize a value between 1 and 0x10000 that is in F */
  98 {
  99     unsigned I;
 100
 101     /* Initialize F */
 102     Initialize (F, Value);
 103
 104     /* If the value is 1 we're already done */
 105     if (Value == 1) {
 106         return;
 107     }
 108
 109     /* Be sure we can factorize */
 110     CHECK (Value <= FAC_MAX && Value != 0);
 111
 112     /* Handle factor 2 separately for speed */
 113     while ((Value & 0x01UL) == 0UL) {
 114         ++F->Powers[0];
 115         Value >>= 1;
 116     }
 117
 118     /* Factorize. */
 119     I = 1;      /* Skip 2 because it was handled above */
 120     while (Value > 1) {
 121         unsigned long Tmp = Value / Primes[I];
 122         if (Tmp * Primes[I] == Value) {
 123             /* This is a factor */
 124             ++F->Powers[I];
 125             Value = Tmp;
 126         } else {
 127             /* This is not a factor, try next one */
 128             if (++I >= PRIME_COUNT) {
 129                 break;
 130             }
 131         }
 132     }
 133
 134     /* If something is left, it must be a remaining prime */
 135     F->Remainder = Value;
 136 }
 137
 138
 139
 140 unsigned long LeastCommonMultiple (unsigned long Left, unsigned long Right)
 141 /* Calculate the least common multiple of two numbers and return
 142  * the result.
 143  */
 144 {
 145     unsigned I;
 146     FactorizedNumber L, R;
 147     unsigned long Res;
 148
 149     /* Factorize the two numbers */
 150     Factorize (Left, &L);
 151     Factorize (Right, &R);
 152
 153     /* Generate the result from the factors.
 154      * Some thoughts on range problems: Since the largest numbers we can
 155      * factorize are 2^16 (0x10000), the only numbers that could produce an
 156      * overflow when using 32 bits are exactly these. But the LCM for 2^16
 157      * and 2^16 is 2^16 so this will never happen and we're safe.
 158      */
 159     Res = L.Remainder * R.Remainder;
 160     for (I = 0; I < PRIME_COUNT; ++I) {
 161         unsigned P = (L.Powers[I] > R.Powers[I])? L.Powers[I] : R.Powers[I];
 162         while (P--) {
 163             Res *= Primes[I];
 164         }
 165     }
 166
 167     /* Return the calculated lcm */
 168     return Res;
 169 }
 170
 171
 172
 173 unsigned long AlignAddr (unsigned long Addr, unsigned long Alignment)
 174 /* Align an address to the given alignment */
 175 {
 176     return ((Addr + Alignment - 1) / Alignment) * Alignment;
 177 }
 178
 179
 180
 181 unsigned long AlignCount (unsigned long Addr, unsigned long Alignment)
 182 /* Calculate how many bytes must be inserted to align Addr to Alignment */
 183 {
 184     return AlignAddr (Addr, Alignment) - Addr;
 185 }
 186
 187
 188