]> git.sur5r.net Git - cc65/blob - src/common/alignment.c
un-remove TABs in doc/using-make.sgml
[cc65] / 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
63
64
65 /* A number together with its prime factors */
66 typedef struct FactorizedNumber FactorizedNumber;
67 struct FactorizedNumber {
68     unsigned long       Value;                  /* The actual number */
69     unsigned long       Remainder;              /* Remaining prime */
70     unsigned char       Powers[PRIME_COUNT];    /* Powers of the factors */
71 };
72
73
74
75 /*****************************************************************************/
76 /*                                   Code                                    */
77 /*****************************************************************************/
78
79
80
81 static void Initialize (FactorizedNumber* F, unsigned long Value)
82 /* Initialize a FactorizedNumber structure */
83 {
84     unsigned I;
85
86     F->Value = Value;
87     F->Remainder = 1;
88     for (I = 0; I < PRIME_COUNT; ++I) {
89         F->Powers[I] = 0;
90     }
91 }
92
93
94
95 static void Factorize (unsigned long Value, FactorizedNumber* F)
96 /* Factorize a value between 1 and 0x10000 that is in F */
97 {
98     unsigned I;
99
100     /* Initialize F */
101     Initialize (F, Value);
102
103     /* If the value is 1 we're already done */
104     if (Value == 1) {
105         return;
106     }
107
108     /* Be sure we can factorize */
109     CHECK (Value <= MAX_ALIGNMENT && Value != 0);
110
111     /* Handle factor 2 separately for speed */
112     while ((Value & 0x01UL) == 0UL) {
113         ++F->Powers[0];
114         Value >>= 1;
115     }
116
117     /* Factorize. */
118     I = 1;      /* Skip 2 because it was handled above */
119     while (Value > 1) {
120         unsigned long Tmp = Value / Primes[I];
121         if (Tmp * Primes[I] == Value) {
122             /* This is a factor */
123             ++F->Powers[I];
124             Value = Tmp;
125         } else {
126             /* This is not a factor, try next one */
127             if (++I >= PRIME_COUNT) {
128                 break;
129             }
130         }
131     }
132
133     /* If something is left, it must be a remaining prime */
134     F->Remainder = Value;
135 }
136
137
138
139 unsigned long LeastCommonMultiple (unsigned long Left, unsigned long Right)
140 /* Calculate the least common multiple of two numbers and return
141 ** the result.
142 */
143 {
144     unsigned I;
145     FactorizedNumber L, R;
146     unsigned long Res;
147
148     /* Factorize the two numbers */
149     Factorize (Left, &L);
150     Factorize (Right, &R);
151
152     /* Generate the result from the factors.
153     ** Some thoughts on range problems: Since the largest numbers we can
154     ** factorize are 2^16 (0x10000), the only numbers that could produce an
155     ** overflow when using 32 bits are exactly these. But the LCM for 2^16
156     ** and 2^16 is 2^16 so this will never happen and we're safe.
157     */
158     Res = L.Remainder * R.Remainder;
159     for (I = 0; I < PRIME_COUNT; ++I) {
160         unsigned P = (L.Powers[I] > R.Powers[I])? L.Powers[I] : R.Powers[I];
161         while (P--) {
162             Res *= Primes[I];
163         }
164     }
165
166     /* Return the calculated lcm */
167     return Res;
168 }
169
170
171
172 unsigned long AlignAddr (unsigned long Addr, unsigned long Alignment)
173 /* Align an address to the given alignment */
174 {
175     return ((Addr + Alignment - 1) / Alignment) * Alignment;
176 }
177
178
179
180 unsigned long AlignCount (unsigned long Addr, unsigned long Alignment)
181 /* Calculate how many bytes must be inserted to align Addr to Alignment */
182 {
183     return AlignAddr (Addr, Alignment) - Addr;
184 }