Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 4758 | right-hear | 1 | /* |
| 2 | * Copyright (c) 2002-2007, Communications and Remote Sensing Laboratory, Universite catholique de Louvain (UCL), Belgium |
||
| 3 | * Copyright (c) 2002-2007, Professor Benoit Macq |
||
| 4 | * Copyright (c) 2001-2003, David Janssens |
||
| 5 | * Copyright (c) 2002-2003, Yannick Verschueren |
||
| 6 | * Copyright (c) 2003-2007, Francois-Olivier Devaux and Antonin Descampe |
||
| 7 | * Copyright (c) 2005, Herve Drolon, FreeImage Team |
||
| 8 | * All rights reserved. |
||
| 9 | * |
||
| 10 | * Redistribution and use in source and binary forms, with or without |
||
| 11 | * modification, are permitted provided that the following conditions |
||
| 12 | * are met: |
||
| 13 | * 1. Redistributions of source code must retain the above copyright |
||
| 14 | * notice, this list of conditions and the following disclaimer. |
||
| 15 | * 2. Redistributions in binary form must reproduce the above copyright |
||
| 16 | * notice, this list of conditions and the following disclaimer in the |
||
| 17 | * documentation and/or other materials provided with the distribution. |
||
| 18 | * |
||
| 19 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS' |
||
| 20 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
||
| 21 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
||
| 22 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
||
| 23 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
||
| 24 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
||
| 25 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
||
| 26 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
||
| 27 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
||
| 28 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
||
| 29 | * POSSIBILITY OF SUCH DAMAGE. |
||
| 30 | */ |
||
| 31 | |||
| 32 | #include "opj_includes.h" |
||
| 33 | |||
| 34 | /* |
||
| 35 | ========================================================== |
||
| 36 | Tag-tree coder interface |
||
| 37 | ========================================================== |
||
| 38 | */ |
||
| 39 | |||
| 40 | opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv) { |
||
| 41 | int nplh[32]; |
||
| 42 | int nplv[32]; |
||
| 43 | opj_tgt_node_t *node = NULL; |
||
| 44 | opj_tgt_node_t *parentnode = NULL; |
||
| 45 | opj_tgt_node_t *parentnode0 = NULL; |
||
| 46 | opj_tgt_tree_t *tree = NULL; |
||
| 47 | int i, j, k; |
||
| 48 | int numlvls; |
||
| 49 | int n; |
||
| 50 | |||
| 51 | tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t)); |
||
| 52 | if(!tree) return NULL; |
||
| 53 | tree->numleafsh = numleafsh; |
||
| 54 | tree->numleafsv = numleafsv; |
||
| 55 | |||
| 56 | numlvls = 0; |
||
| 57 | nplh[0] = numleafsh; |
||
| 58 | nplv[0] = numleafsv; |
||
| 59 | tree->numnodes = 0; |
||
| 60 | do { |
||
| 61 | n = nplh[numlvls] * nplv[numlvls]; |
||
| 62 | nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2; |
||
| 63 | nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2; |
||
| 64 | tree->numnodes += n; |
||
| 65 | ++numlvls; |
||
| 66 | } while (n > 1); |
||
| 67 | |||
| 68 | /* ADD */ |
||
| 69 | if (tree->numnodes == 0) { |
||
| 70 | opj_free(tree); |
||
| 71 | return NULL; |
||
| 72 | } |
||
| 73 | |||
| 74 | tree->nodes = (opj_tgt_node_t*) opj_calloc(tree->numnodes, sizeof(opj_tgt_node_t)); |
||
| 75 | if(!tree->nodes) { |
||
| 76 | opj_free(tree); |
||
| 77 | return NULL; |
||
| 78 | } |
||
| 79 | |||
| 80 | node = tree->nodes; |
||
| 81 | parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv]; |
||
| 82 | parentnode0 = parentnode; |
||
| 83 | |||
| 84 | for (i = 0; i < numlvls - 1; ++i) { |
||
| 85 | for (j = 0; j < nplv[i]; ++j) { |
||
| 86 | k = nplh[i]; |
||
| 87 | while (--k >= 0) { |
||
| 88 | node->parent = parentnode; |
||
| 89 | ++node; |
||
| 90 | if (--k >= 0) { |
||
| 91 | node->parent = parentnode; |
||
| 92 | ++node; |
||
| 93 | } |
||
| 94 | ++parentnode; |
||
| 95 | } |
||
| 96 | if ((j & 1) || j == nplv[i] - 1) { |
||
| 97 | parentnode0 = parentnode; |
||
| 98 | } else { |
||
| 99 | parentnode = parentnode0; |
||
| 100 | parentnode0 += nplh[i]; |
||
| 101 | } |
||
| 102 | } |
||
| 103 | } |
||
| 104 | node->parent = 0; |
||
| 105 | |||
| 106 | tgt_reset(tree); |
||
| 107 | |||
| 108 | return tree; |
||
| 109 | } |
||
| 110 | |||
| 111 | void tgt_destroy(opj_tgt_tree_t *tree) { |
||
| 112 | opj_free(tree->nodes); |
||
| 113 | opj_free(tree); |
||
| 114 | } |
||
| 115 | |||
| 116 | void tgt_reset(opj_tgt_tree_t *tree) { |
||
| 117 | int i; |
||
| 118 | |||
| 119 | if (NULL == tree) |
||
| 120 | return; |
||
| 121 | |||
| 122 | for (i = 0; i < tree->numnodes; i++) { |
||
| 123 | tree->nodes[i].value = 999; |
||
| 124 | tree->nodes[i].low = 0; |
||
| 125 | tree->nodes[i].known = 0; |
||
| 126 | } |
||
| 127 | } |
||
| 128 | |||
| 129 | void tgt_setvalue(opj_tgt_tree_t *tree, int leafno, int value) { |
||
| 130 | opj_tgt_node_t *node; |
||
| 131 | node = &tree->nodes[leafno]; |
||
| 132 | while (node && node->value > value) { |
||
| 133 | node->value = value; |
||
| 134 | node = node->parent; |
||
| 135 | } |
||
| 136 | } |
||
| 137 | |||
| 138 | void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) { |
||
| 139 | opj_tgt_node_t *stk[31]; |
||
| 140 | opj_tgt_node_t **stkptr; |
||
| 141 | opj_tgt_node_t *node; |
||
| 142 | int low; |
||
| 143 | |||
| 144 | stkptr = stk; |
||
| 145 | node = &tree->nodes[leafno]; |
||
| 146 | while (node->parent) { |
||
| 147 | *stkptr++ = node; |
||
| 148 | node = node->parent; |
||
| 149 | } |
||
| 150 | |||
| 151 | low = 0; |
||
| 152 | for (;;) { |
||
| 153 | if (low > node->low) { |
||
| 154 | node->low = low; |
||
| 155 | } else { |
||
| 156 | low = node->low; |
||
| 157 | } |
||
| 158 | |||
| 159 | while (low < threshold) { |
||
| 160 | if (low >= node->value) { |
||
| 161 | if (!node->known) { |
||
| 162 | bio_write(bio, 1, 1); |
||
| 163 | node->known = 1; |
||
| 164 | } |
||
| 165 | break; |
||
| 166 | } |
||
| 167 | bio_write(bio, 0, 1); |
||
| 168 | ++low; |
||
| 169 | } |
||
| 170 | |||
| 171 | node->low = low; |
||
| 172 | if (stkptr == stk) |
||
| 173 | break; |
||
| 174 | node = *--stkptr; |
||
| 175 | } |
||
| 176 | } |
||
| 177 | |||
| 178 | int tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) { |
||
| 179 | opj_tgt_node_t *stk[31]; |
||
| 180 | opj_tgt_node_t **stkptr; |
||
| 181 | opj_tgt_node_t *node; |
||
| 182 | int low; |
||
| 183 | |||
| 184 | stkptr = stk; |
||
| 185 | node = &tree->nodes[leafno]; |
||
| 186 | while (node->parent) { |
||
| 187 | *stkptr++ = node; |
||
| 188 | node = node->parent; |
||
| 189 | } |
||
| 190 | |||
| 191 | low = 0; |
||
| 192 | for (;;) { |
||
| 193 | if (low > node->low) { |
||
| 194 | node->low = low; |
||
| 195 | } else { |
||
| 196 | low = node->low; |
||
| 197 | } |
||
| 198 | while (low < threshold && low < node->value) { |
||
| 199 | if (bio_read(bio, 1)) { |
||
| 200 | node->value = low; |
||
| 201 | } else { |
||
| 202 | ++low; |
||
| 203 | } |
||
| 204 | } |
||
| 205 | node->low = low; |
||
| 206 | if (stkptr == stk) { |
||
| 207 | break; |
||
| 208 | } |
||
| 209 | node = *--stkptr; |
||
| 210 | } |
||
| 211 | |||
| 212 | return (node->value < threshold) ? 1 : 0; |
||
| 213 | } |