1 /*
2 * This file is part of the Advance project.
3 *
4 * Copyright (C) 2002, 2003 Andrea Mazzoleni
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21 #include "portable.h"
22
23 #include "scroll.h"
24 #include "data.h"
25
26 #if defined(__GNUC__) && defined(__i386__)
27 #define USE_MMX 1
28 #endif
29
compare_line(unsigned width,unsigned height,unsigned char * p0,unsigned char * p1,unsigned line)30 static unsigned compare_line(unsigned width, unsigned height, unsigned char* p0, unsigned char* p1, unsigned line)
31 {
32 unsigned i, j;
33 unsigned count = 0;
34
35 for(i=0;i<height;++i) {
36 #if defined(USE_MMX)
37 /* MMX ASM optimized version */
38 j = width;
39 while (j >= 8) {
40 unsigned char data[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1 };
41
42 unsigned run = j / 8;
43
44 if (run > 255)
45 run = 255; /* prevent overflow in the sum byte registers */
46
47 j = j - run * 8;
48
49 __asm__ __volatile__(
50 "movq 0(%3), %%mm2\n"
51 "movq 8(%3), %%mm3\n"
52
53 "0:\n"
54
55 "movq 0(%0), %%mm0\n"
56 "movq 0(%1), %%mm1\n"
57
58 "pcmpeqb %%mm0, %%mm1\n"
59 "pand %%mm3, %%mm1\n"
60 "paddb %%mm1, %%mm2\n"
61
62 "addl $8, %0\n"
63 "addl $8, %1\n"
64
65 "decl %2\n"
66 "jnz 0b\n"
67
68 "movq %%mm2, 0(%3)\n"
69
70 : "+r" (p0), "+r" (p1), "+r" (run)
71 : "r" (data)
72 : "cc", "memory"
73 );
74
75 count += data[0];
76 count += data[1];
77 count += data[2];
78 count += data[3];
79 count += data[4];
80 count += data[5];
81 count += data[6];
82 count += data[7];
83 }
84 while (j > 0) {
85 if (p0[0] == p1[0])
86 ++count;
87 ++p0;
88 ++p1;
89 --j;
90 }
91 #else
92 #if defined(USE_OPTC)
93 /* C optimized version */
94 j = width;
95 while (j >= 4) {
96 unsigned v0 = *(unsigned*)p0;
97 unsigned v1 = *(unsigned*)p1;
98 v0 ^= v1;
99 if (v0) {
100 if ((v0 & 0x000000FF) == 0)
101 ++count;
102 if ((v0 & 0x0000FF00) == 0)
103 ++count;
104 if ((v0 & 0x00FF0000) == 0)
105 ++count;
106 if ((v0 & 0xFF000000) == 0)
107 ++count;
108 } else {
109 count += 4;
110 }
111 p0 += 4;
112 p1 += 4;
113 j -= 4;
114 }
115 while (j > 0) {
116 if (p0[0] == p1[0])
117 ++count;
118 ++p0;
119 ++p1;
120 --j;
121 }
122 #else
123 /* standard C implementation */
124 for(j=0;j<width;++j) {
125 if (p0[0] == p1[0])
126 ++count;
127 ++p0;
128 ++p1;
129 }
130 #endif
131 #endif
132 p0 += line - width;
133 p1 += line - width;
134 }
135
136 #if defined(USE_MMX)
137 __asm__ __volatile__ (
138 "emms"
139 );
140 #endif
141
142 return count;
143 }
144
compare_shift(int x,int y,unsigned width,unsigned height,unsigned char * p0,unsigned char * p1,unsigned pixel,unsigned line)145 static unsigned compare_shift(int x, int y, unsigned width, unsigned height, unsigned char* p0, unsigned char* p1, unsigned pixel, unsigned line)
146 {
147 unsigned count;
148
149 int dx = width - abs(x);
150 int dy = height - abs(y);
151
152 if (x < 0)
153 p1 += -x * pixel;
154 else
155 p0 += x * pixel;
156
157 if (y < 0)
158 p1 += -y * line;
159 else
160 p0 += y * line;
161
162 if (pixel == 1) {
163 count = compare_line(dx, dy, p0, p1, line);
164 } else {
165 /* the exact number of equal pixels isn't really required, the */
166 /* number of equal channels also works well */
167 count = compare_line(dx*3, dy, p0, p1, line) / 3;
168 }
169
170 return count;
171 }
172
compare(adv_scroll * scroll,int * x,int * y,unsigned width,unsigned height,unsigned char * p0,unsigned char * p1,unsigned pixel,unsigned line)173 static void compare(adv_scroll* scroll, int* x, int* y, unsigned width, unsigned height, unsigned char* p0, unsigned char* p1, unsigned pixel, unsigned line)
174 {
175 int i, j;
176 int best_x;
177 int best_y;
178 unsigned best_count;
179 unsigned prev_count;
180 unsigned total;
181
182 best_x = 0;
183 best_y = 0;
184 best_count = compare_shift(0, 0, width, height, p0, p1, pixel, line);
185
186 prev_count = 0;
187
188 total = width * height;
189
190 for(i=-scroll->range_dx;i<=scroll->range_dx;++i) {
191 for(j=-scroll->range_dy;j<=scroll->range_dy;++j) {
192 if ((j || i) && (abs(i)+abs(j)<=scroll->range_limit)) {
193 unsigned count;
194
195 count = compare_shift(i, j, width, height, p0, p1, pixel, line);
196 if (count > best_count) {
197 prev_count = best_count;
198 best_count = count;
199 best_x = i;
200 best_y = j;
201 } else if (count > prev_count) {
202 prev_count = count;
203 }
204 }
205 }
206 }
207
208 /* if the number of matching pixel is too small don't scroll */
209 if (best_count < total / 4) {
210 *x = 0;
211 *y = 0;
212 } else {
213 *x = best_x;
214 *y = best_y;
215 }
216 }
217
insert(adv_scroll_info * info,int x,int y)218 static void insert(adv_scroll_info* info, int x, int y)
219 {
220 if (info->mac == info->max) {
221 info->max *= 2;
222 if (!info->max)
223 info->max = 64;
224 info->map = (adv_scroll_coord*)realloc(info->map, info->max * sizeof(adv_scroll_coord));
225 }
226
227 info->map[info->mac].x = x;
228 info->map[info->mac].y = y;
229 ++info->mac;
230 }
231
scroll_analyze(adv_scroll * scroll,unsigned pix_width,unsigned pix_height,unsigned pix_pixel,unsigned char * pix_ptr,unsigned pix_scanline)232 void scroll_analyze(adv_scroll* scroll, unsigned pix_width, unsigned pix_height, unsigned pix_pixel, unsigned char* pix_ptr, unsigned pix_scanline)
233 {
234 unsigned char* ptr;
235 unsigned scanline;
236 unsigned i;
237
238 scanline = pix_width * pix_pixel;
239 ptr = data_alloc(pix_height * scanline);
240
241 for(i=0;i<pix_height;++i) {
242 memcpy(ptr + i*scanline, pix_ptr + i*pix_scanline, scanline);
243 }
244
245 data_free(scroll->pre_ptr);
246 scroll->pre_ptr = scroll->cur_ptr;
247 scroll->cur_ptr = ptr;
248
249 if (scroll->pre_ptr && scroll->cur_ptr) {
250 int x;
251 int y;
252 compare(scroll, &x, &y, pix_width, pix_height, scroll->pre_ptr, scroll->cur_ptr, pix_pixel, scanline);
253 insert(scroll->info, x, y);
254 } else {
255 insert(scroll->info, 0, 0);
256 }
257 }
258
postprocessing(adv_scroll_info * info)259 static void postprocessing(adv_scroll_info* info)
260 {
261 int px = 0;
262 int py = 0;
263 int min_x = 0;
264 int min_y = 0;
265 int max_x = 0;
266 int max_y = 0;
267 unsigned i;
268
269 for(i=0;i<info->mac;++i) {
270 px += info->map[i].x;
271 py += info->map[i].y;
272 if (px < min_x)
273 min_x = px;
274 if (py < min_y)
275 min_y = py;
276 if (px > max_x)
277 max_x = px;
278 if (py > max_y)
279 max_y = py;
280 }
281
282 info->x = -min_x;
283 info->y = -min_y;
284 info->width = max_x - min_x;
285 info->height = max_y - min_y;
286 }
287
scroll_init(int dx,int dy,int limit)288 adv_scroll* scroll_init(int dx, int dy, int limit)
289 {
290 adv_scroll* scroll = (adv_scroll*)malloc(sizeof(adv_scroll));
291
292 scroll->info = (adv_scroll_info*)malloc(sizeof(adv_scroll_info));
293
294 scroll->info->map = 0;
295 scroll->info->mac = 0;
296 scroll->info->max = 0;
297
298 scroll->range_dx = dx;
299 scroll->range_dy = dy;
300 scroll->range_limit = limit;
301
302 scroll->cur_ptr = 0;
303 scroll->pre_ptr = 0;
304
305 return scroll;
306 }
307
scroll_last_get(adv_scroll * scroll,int * x,int * y)308 void scroll_last_get(adv_scroll* scroll, int* x, int* y)
309 {
310 if (!scroll->info || !scroll->info->mac) {
311 *x = 0;
312 *y = 0;
313 } else {
314 *x = scroll->info->map[scroll->info->mac-1].x;
315 *y = scroll->info->map[scroll->info->mac-1].y;
316 }
317 }
318
scroll_info_init(adv_scroll * scroll)319 adv_scroll_info* scroll_info_init(adv_scroll* scroll)
320 {
321 adv_scroll_info* info = scroll->info;
322
323 postprocessing(info);
324
325 scroll->info = 0;
326
327 return info;
328 }
329
scroll_info_done(adv_scroll_info * info)330 void scroll_info_done(adv_scroll_info* info)
331 {
332 free(info->map);
333 free(info);
334 }
335
scroll_done(adv_scroll * scroll)336 void scroll_done(adv_scroll* scroll)
337 {
338 data_free(scroll->pre_ptr);
339 data_free(scroll->cur_ptr);
340 if (scroll->info)
341 scroll_info_done(scroll->info);
342 free(scroll);
343 }
344
345