1 /*****************************************************************************/
9 /* (C) 2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* 70794 Filderstadt */
12 /* EMail: uz@cc65.org */
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. */
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: */
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 */
32 /*****************************************************************************/
37 #include "alignment.h"
42 /*****************************************************************************/
44 /*****************************************************************************/
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.
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,
60 #define PRIME_COUNT (sizeof (Primes) / sizeof (Primes[0]))
61 #define LAST_PRIME ((unsigned long)Primes[PRIME_COUNT-1])
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 */
75 /*****************************************************************************/
77 /*****************************************************************************/
81 static void Initialize (FactorizedNumber* F, unsigned long Value)
82 /* Initialize a FactorizedNumber structure */
88 for (I = 0; I < PRIME_COUNT; ++I) {
95 static void Factorize (unsigned long Value, FactorizedNumber* F)
96 /* Factorize a value between 1 and 0x10000 that is in F */
101 Initialize (F, Value);
103 /* If the value is 1 we're already done */
108 /* Be sure we can factorize */
109 CHECK (Value <= MAX_ALIGNMENT && Value != 0);
111 /* Handle factor 2 separately for speed */
112 while ((Value & 0x01UL) == 0UL) {
118 I = 1; /* Skip 2 because it was handled above */
120 unsigned long Tmp = Value / Primes[I];
121 if (Tmp * Primes[I] == Value) {
122 /* This is a factor */
126 /* This is not a factor, try next one */
127 if (++I >= PRIME_COUNT) {
133 /* If something is left, it must be a remaining prime */
134 F->Remainder = Value;
139 unsigned long LeastCommonMultiple (unsigned long Left, unsigned long Right)
140 /* Calculate the least common multiple of two numbers and return
145 FactorizedNumber L, R;
148 /* Factorize the two numbers */
149 Factorize (Left, &L);
150 Factorize (Right, &R);
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.
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];
166 /* Return the calculated lcm */
172 unsigned long AlignAddr (unsigned long Addr, unsigned long Alignment)
173 /* Align an address to the given alignment */
175 return ((Addr + Alignment - 1) / Alignment) * Alignment;
180 unsigned long AlignCount (unsigned long Addr, unsigned long Alignment)
181 /* Calculate how many bytes must be inserted to align Addr to Alignment */
183 return AlignAddr (Addr, Alignment) - Addr;