1/*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17// pyramid.cpp
18
19#include <stdio.h>
20#include <string.h>
21
22#include "Pyramid.h"
23
24// We allocate the entire pyramid into one contiguous storage. This makes
25// cleanup easier than fragmented stuff. In addition, we added a "pitch"
26// field, so pointer manipulation is much simpler when it would be faster.
27PyramidShort *PyramidShort::allocatePyramidPacked(real levels,
28        real width, real height, real border)
29{
30    real border2 = (real) (border << 1);
31    int lines, size = calcStorage(width, height, border2, levels, &lines);
32
33    PyramidShort *img = (PyramidShort *) calloc(sizeof(PyramidShort) * levels
34            + sizeof(short *) * lines +
35            + sizeof(short) * size, 1);
36
37    if (img) {
38        PyramidShort *curr, *last;
39        ImageTypeShort *y = (ImageTypeShort *) &img[levels];
40        ImageTypeShort position = (ImageTypeShort) &y[lines];
41        for (last = (curr = img) + levels; curr < last; curr++) {
42            curr->width = width;
43            curr->height = height;
44            curr->border = border;
45            curr->pitch = (real) (width + border2);
46            curr->ptr = y + border;
47
48            // Assign row pointers
49            for (int j = height + border2; j--; y++, position += curr->pitch) {
50                *y = position + border;
51            }
52
53            width >>= 1;
54            height >>= 1;
55        }
56    }
57
58    return img;
59}
60
61// Allocate an image of type short
62PyramidShort *PyramidShort::allocateImage(real width, real height, real border)
63{
64    real border2 = (real) (border << 1);
65    PyramidShort *img = (PyramidShort *)
66        calloc(sizeof(PyramidShort) + sizeof(short *) * (height + border2) +
67                sizeof(short) * (width + border2) * (height + border2), 1);
68
69    if (img) {
70        short **y = (short **) &img[1];
71        short *position = (short *) &y[height + border2];
72        img->width = width;
73        img->height = height;
74        img->border = border;
75        img->pitch = (real) (width + border2);
76        img->ptr = y + border;
77        position += border; // Move position down to origin of real image
78
79        // Assign row pointers
80        for (int j = height + border2; j--; y++, position += img->pitch) {
81            *y = position;
82        }
83    }
84
85    return img;
86}
87
88// Free the images
89void PyramidShort::freeImage(PyramidShort *image)
90{
91    if (image != NULL)
92        free(image);
93}
94
95// Calculate amount of storage needed taking into account the borders, etc.
96unsigned int PyramidShort::calcStorage(real width, real height, real border2,   int levels, int *lines)
97{
98    int size;
99
100    *lines = size = 0;
101
102    while(levels--) {
103        size += (width + border2) * (height + border2);
104        *lines += height + border2;
105        width >>= 1;
106        height >>= 1;
107    }
108
109    return size;
110}
111
112void PyramidShort::BorderSpread(PyramidShort *pyr, int left, int right,
113        int top, int bot)
114{
115    int off, off2, height, h, w;
116    ImageTypeShort base;
117
118    if (left || right) {
119        off = pyr->border - left;
120        off2 = pyr->width + off + pyr->border - right - 1;
121        h = pyr->border - top;
122        height = pyr->height + (h << 1);
123        base = pyr->ptr[-h] - off;
124
125        // spread in X
126        for (h = height; h--; base += pyr->pitch) {
127            for (w = left; w--;)
128                base[-1 - w] = base[0];
129            for (w = right; w--;)
130                base[off2 + w + 1] = base[off2];
131        }
132    }
133
134    if (top || bot) {
135        // spread in Y
136        base = pyr->ptr[top - pyr->border] - pyr->border;
137        for (h = top; h--; base -= pyr->pitch) {
138            memcpy(base - pyr->pitch, base, pyr->pitch * sizeof(short));
139        }
140
141        base = pyr->ptr[pyr->height + pyr->border - bot] - pyr->border;
142        for (h = bot; h--; base += pyr->pitch) {
143            memcpy(base, base - pyr->pitch, pyr->pitch * sizeof(short));
144        }
145    }
146}
147
148void PyramidShort::BorderExpandOdd(PyramidShort *in, PyramidShort *out, PyramidShort *scr,
149        int mode)
150{
151    int i,j;
152    int off = in->border / 2;
153
154    // Vertical Filter
155    for (j = -off; j < in->height + off; j++) {
156        int j2 = j * 2;
157        for (i = -scr->border; i < scr->width + scr->border; i++) {
158            scr->ptr[j2][i] = (short)
159                ((6 * in->ptr[j][i] + (in->ptr[j-1][i] + in->ptr[j+1][i]) + 4) >> 3);
160            scr->ptr[j2+1][i] = (short)((in->ptr[j][i] + in->ptr[j+1][i] + 1) >> 1);
161        }
162    }
163
164    BorderSpread(scr, 0, 0, 3, 3);
165
166    // Horizontal Filter
167    for (i = -off; i < scr->width + off; i++) {
168        int i2 = i * 2;
169        for (j = -out->border; j < out->height + out->border; j++) {
170            out->ptr[j][i2] = (short) (out->ptr[j][i2] +
171                    (mode * ((6 * scr->ptr[j][i] +
172                              scr->ptr[j][i-1] + scr->ptr[j][i+1] + 4) >> 3)));
173            out->ptr[j][i2+1] = (short) (out->ptr[j][i2+1] +
174                    (mode * ((scr->ptr[j][i] + scr->ptr[j][i+1] + 1) >> 1)));
175        }
176    }
177
178}
179
180int PyramidShort::BorderExpand(PyramidShort *pyr, int nlev, int mode)
181{
182    PyramidShort *tpyr = pyr + nlev - 1;
183    PyramidShort *scr = allocateImage(pyr[1].width, pyr[0].height, pyr->border);
184    if (scr == NULL) return 0;
185
186    if (mode > 0) {
187        // Expand and add (reconstruct from Laplacian)
188        for (; tpyr > pyr; tpyr--) {
189            scr->width = tpyr[0].width;
190            scr->height = tpyr[-1].height;
191            BorderExpandOdd(tpyr, tpyr - 1, scr, 1);
192        }
193    }
194    else if (mode < 0) {
195        // Expand and subtract (build Laplacian)
196        while ((pyr++) < tpyr) {
197            scr->width = pyr[0].width;
198            scr->height = pyr[-1].height;
199            BorderExpandOdd(pyr, pyr - 1, scr, -1);
200        }
201    }
202
203    freeImage(scr);
204    return 1;
205}
206
207void PyramidShort::BorderReduceOdd(PyramidShort *in, PyramidShort *out, PyramidShort *scr)
208{
209    ImageTypeShortBase *s, *ns, *ls, *p, *np;
210
211    int off = scr->border - 2;
212    s = scr->ptr[-scr->border] - (off >> 1);
213    ns = s + scr->pitch;
214    ls = scr->ptr[scr->height + scr->border - 1] + scr->pitch - (off >> 1);
215    int width = scr->width + scr->border;
216    p = in->ptr[-scr->border] - off;
217    np = p + in->pitch;
218
219    // treat it as if the whole thing were the image
220    for (; s < ls; s = ns, ns += scr->pitch, p = np, np += in->pitch) {
221        for (int w = width; w--; s++, p += 2) {
222            *s = (short)((((int) p[-2]) + ((int) p[2]) + 8 +    // 1
223                        ((((int) p[-1]) + ((int) p[1])) << 2) + // 4
224                        ((int) *p) * 6) >> 4);          // 6
225        }
226    }
227
228    BorderSpread(scr, 5, 4 + ((in->width ^ 1) & 1), 0, 0); //
229
230    s = out->ptr[-(off >> 1)] - out->border;
231    ns = s + out->pitch;
232    ls = s + out->pitch * (out->height + off);
233    p = scr->ptr[-off] - out->border;
234    int pitch = scr->pitch;
235    int pitch2 = pitch << 1;
236    np = p + pitch2;
237    for (; s < ls; s = ns, ns += out->pitch, p = np, np += pitch2) {
238        for (int w = out->pitch; w--; s++, p++) {
239            *s = (short)((((int) p[-pitch2]) + ((int) p[pitch2]) + 8 + // 1
240                        ((((int) p[-pitch]) + ((int) p[pitch])) << 2) + // 4
241                        ((int) *p) * 6) >> 4);              // 6
242        }
243    }
244    BorderSpread(out, 0, 0, 5, 5);
245
246}
247
248int PyramidShort::BorderReduce(PyramidShort *pyr, int nlev)
249{
250    PyramidShort *scr = allocateImage(pyr[1].width, pyr[0].height, pyr->border);
251    if (scr == NULL)
252        return 0;
253
254    BorderSpread(pyr, pyr->border, pyr->border, pyr->border, pyr->border);
255    while (--nlev) {
256        BorderReduceOdd(pyr, pyr + 1, scr);
257        pyr++;
258        scr->width = pyr[1].width;
259        scr->height = pyr[0].height;
260    }
261
262    freeImage(scr);
263    return 1;
264}
265