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*/
52static 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 */
66typedef struct FactorizedNumber FactorizedNumber;
67struct 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
81static 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
95static 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
139unsigned 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
172unsigned 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
180unsigned 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}
185