1 |
/* |
2 |
* Copyright (C) 2005 Anders Gavare. All rights reserved. |
3 |
* |
4 |
* Redistribution and use in source and binary forms, with or without |
5 |
* modification, are permitted provided that the following conditions are met: |
6 |
* |
7 |
* 1. Redistributions of source code must retain the above copyright |
8 |
* notice, this list of conditions and the following disclaimer. |
9 |
* 2. Redistributions in binary form must reproduce the above copyright |
10 |
* notice, this list of conditions and the following disclaimer in the |
11 |
* documentation and/or other materials provided with the distribution. |
12 |
* 3. The name of the author may not be used to endorse or promote products |
13 |
* derived from this software without specific prior written permission. |
14 |
* |
15 |
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
16 |
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
17 |
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
18 |
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
19 |
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
20 |
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
21 |
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
22 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
23 |
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
24 |
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
25 |
* SUCH DAMAGE. |
26 |
* |
27 |
* |
28 |
* $Id: experiment_arm_multi.c,v 1.1 2005/10/22 09:38:46 debug Exp $ |
29 |
* |
30 |
* Given a list of common ARM load/store multiple opcodes, figure out (using |
31 |
* simple brute force), which n bits (where n is low, e.g. 7) that cause the |
32 |
* best separation of the 24 bit opcode space into linear lists, where "best" |
33 |
* means to optimize the length of the longest such linear list. |
34 |
* |
35 |
* The result is a set of bits, such as this: |
36 |
* |
37 |
* xxxx100P USWLnnnn llllllll llllllll |
38 |
* ^ ^ ^^ ^^ (in this case, n = 6) |
39 |
* |
40 |
* (it's a 24-bit space, because the s-bit isn't used). |
41 |
*/ |
42 |
|
43 |
#include <stdio.h> |
44 |
#include <stdlib.h> |
45 |
|
46 |
|
47 |
int bit_count(unsigned int x) |
48 |
{ |
49 |
static const int c[16] = { 0,1,1,2, 1,2,2,3, 1,2,2,3, 2,3,3,4 }; |
50 |
return c[x & 15] + c[(x>>4) & 15] + |
51 |
c[(x>>8) & 15] + c[(x>>12) & 15] + |
52 |
c[(x>>16) & 15] + c[(x>>20) & 15] + |
53 |
c[(x>>24) & 15] + c[(x>>28) & 15]; |
54 |
} |
55 |
|
56 |
|
57 |
int cmpfunc(const void *a, const void *b) |
58 |
{ |
59 |
int *pa = (int *) a, *pb = (int *) b; |
60 |
if (*pa < *pb) |
61 |
return -1; |
62 |
if (*pa > *pb) |
63 |
return 1; |
64 |
return 0; |
65 |
} |
66 |
|
67 |
|
68 |
int calc_max_list_length(int *opcodes, int *tmp_table, |
69 |
int n_opcodes, int bit_mask) |
70 |
{ |
71 |
int i, maxlen, curlen; |
72 |
|
73 |
for (i=0; i<n_opcodes; i++) |
74 |
tmp_table[i] = opcodes[i] & bit_mask; |
75 |
|
76 |
qsort(tmp_table, n_opcodes, sizeof(int), cmpfunc); |
77 |
curlen = maxlen = 1; |
78 |
|
79 |
for (i=1; i<n_opcodes; i++) |
80 |
if (tmp_table[i] == tmp_table[i-1]) { |
81 |
curlen ++; |
82 |
if (curlen > maxlen) |
83 |
maxlen = curlen; |
84 |
} else |
85 |
curlen = 1; |
86 |
|
87 |
return maxlen; |
88 |
} |
89 |
|
90 |
|
91 |
int main(int argc, char *argv[]) |
92 |
{ |
93 |
FILE *f = fopen("cpu_arm_multi.txt", "r"); |
94 |
int n; |
95 |
const int max = 10000; |
96 |
int opcode[max]; |
97 |
int tmp_table[max]; |
98 |
int n_opcodes = 0; |
99 |
int *max_len; |
100 |
int bit_mask, best_bit_mask, best_bit_mask_len; |
101 |
|
102 |
if (argc < 2) { |
103 |
fprintf(stderr, "usage: %s n\n", argv[0]); |
104 |
fprintf(stderr, "where n=6 might be a good choice\n"); |
105 |
exit(1); |
106 |
} |
107 |
|
108 |
n = atoi(argv[1]); |
109 |
|
110 |
if (f == NULL) { |
111 |
fprintf(stderr, "could not open cpu_arm_multi.txt\n"); |
112 |
exit(1); |
113 |
} |
114 |
|
115 |
/* Read the opcodes: */ |
116 |
while (!feof(f)) { |
117 |
char s[100]; |
118 |
s[0] = s[sizeof(s)-1] = '\0'; |
119 |
fgets(s, sizeof(s), f); |
120 |
if (s[0] == '0') { |
121 |
if (n_opcodes > max) { |
122 |
fprintf(stderr, "too many opcodes\n"); |
123 |
exit(1); |
124 |
} |
125 |
opcode[n_opcodes++] = strtol(s, NULL, 0); |
126 |
} |
127 |
} |
128 |
|
129 |
printf("nr of opcodes = %i\n", n_opcodes); |
130 |
|
131 |
max_len = malloc(sizeof(int) * (1 << 25)); |
132 |
if (max_len == NULL) { |
133 |
fprintf(stderr, "out of memory\n"); |
134 |
exit(1); |
135 |
} |
136 |
|
137 |
best_bit_mask_len = -1; |
138 |
|
139 |
for (bit_mask = 0; bit_mask <= 0x01ffffff; bit_mask ++) { |
140 |
/* Skip the s-bit: */ |
141 |
if (bit_mask & 0x00400000) |
142 |
continue; |
143 |
|
144 |
if (bit_count(bit_mask) != n) |
145 |
continue; |
146 |
|
147 |
/* Calculate the max list length for this bit_mask: */ |
148 |
max_len[bit_mask] = calc_max_list_length(opcode, |
149 |
tmp_table, n_opcodes, bit_mask); |
150 |
|
151 |
if (best_bit_mask_len == -1 || |
152 |
max_len[bit_mask] < best_bit_mask_len) { |
153 |
best_bit_mask_len = max_len[bit_mask]; |
154 |
best_bit_mask = bit_mask; |
155 |
printf("best bit_mask so far: 0x%08x: %i\n", |
156 |
best_bit_mask, best_bit_mask_len); |
157 |
} |
158 |
} |
159 |
|
160 |
return 0; |
161 |
} |
162 |
|