Debian Codegraph @

third_party/etc2comp/EtcLib/EtcCodec/EtcSortedBlockList.cpp

raw
1 /*
2 * Copyright 2015 The Etc2Comp Authors.
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 /*
18 EtcSortedBlockList.cpp
19
20 SortedBlockList is a list of 4x4 blocks that can be used by the "effort" system to prioritize
21 the encoding of the 4x4 blocks.
22
23 The sorting is done with buckets, where each bucket is an indication of how much error each 4x4 block has
24
25 */
26
27 #include "EtcConfig.h"
28 #include "EtcSortedBlockList.h"
29
30 #include "EtcBlock4x4.h"
31
32 #include <stdio.h>
33 #include <string.h>
34 #include <assert.h>
35
36 namespace Etc
37 {
38
39 // ----------------------------------------------------------------------------------------------------
40 // construct an empty list
41 //
42 // allocate enough memory to add all of the image's 4x4 blocks later
43 // allocate enough buckets to sort the blocks
44 //
45 SortedBlockList::SortedBlockList(unsigned int a_uiImageBlocks, unsigned int a_uiBuckets)
46 {
47 m_uiImageBlocks = a_uiImageBlocks;
48 m_iBuckets = (int)a_uiBuckets;
49
50 m_uiAddedBlocks = 0;
51 m_uiSortedBlocks = 0;
52 m_palinkPool = new Link[m_uiImageBlocks];
53 m_pabucket = new Bucket[m_iBuckets];
54 m_fMaxError = 0.0f;
55
56 InitBuckets();
57
58 }
59
60 // ----------------------------------------------------------------------------------------------------
61 //
62 SortedBlockList::~SortedBlockList(void)
63 {
64 delete[] m_palinkPool;
65 delete[] m_pabucket;
66 }
67
68 // ----------------------------------------------------------------------------------------------------
69 // add a 4x4 block to the list
70 // the 4x4 block will be sorted later
71 //
72 void SortedBlockList::AddBlock(Block4x4 *a_pblock)
73 {
74 assert(m_uiAddedBlocks < m_uiImageBlocks);
75 Link *plink = &m_palinkPool[m_uiAddedBlocks++];
76 plink->Init(a_pblock);
77 }
78
79 // ----------------------------------------------------------------------------------------------------
80 // sort all of the 4x4 blocks that have been added to the list
81 //
82 // first, determine the maximum error, then assign an error range to each bucket
83 // next, determine which bucket each 4x4 block belongs to based on the 4x4 block's error
84 // add the 4x4 block to the appropriate bucket
85 // lastly, walk thru the buckets and add each bucket to a sorted linked list
86 //
87 // the resultant sorting is an approximate sorting from most to least error
88 //
89 void SortedBlockList::Sort(void)
90 {
91 assert(m_uiAddedBlocks == m_uiImageBlocks);
92 InitBuckets();
93
94 // find max block error
95 m_fMaxError = -1.0f;
96
97 for (unsigned int uiLink = 0; uiLink < m_uiAddedBlocks; uiLink++)
98 {
99 Link *plinkBlock = &m_palinkPool[uiLink];
100
101 float fBlockError = plinkBlock->GetBlock()->GetError();
102 if (fBlockError > m_fMaxError)
103 {
104 m_fMaxError = fBlockError;
105 }
106 }
107 // prevent divide by zero or divide by negative
108 if (m_fMaxError <= 0.0f)
109 {
110 m_fMaxError = 1.0f;
111 }
112 //used for debugging
113 //int numDone = 0;
114 // put all of the blocks with unfinished encodings into the appropriate bucket
115 m_uiSortedBlocks = 0;
116 for (unsigned int uiLink = 0; uiLink < m_uiAddedBlocks; uiLink++)
117 {
118 Link *plinkBlock = &m_palinkPool[uiLink];
119
120 // if the encoding is done, don't add it to the list
121 if (plinkBlock->GetBlock()->GetEncoding()->IsDone())
122 {
123 //numDone++;
124 continue;
125 }
126
127 // calculate the appropriate sort bucket
128 float fBlockError = plinkBlock->GetBlock()->GetError();
129 int iBucket = (int) floorf(m_iBuckets * fBlockError / m_fMaxError);
130 // clamp to bucket index
131 iBucket = iBucket < 0 ? 0 : iBucket >= m_iBuckets ? m_iBuckets - 1 : iBucket;
132
133 // add block to bucket
134 {
135 Bucket *pbucket = &m_pabucket[iBucket];
136 if (pbucket->plinkLast)
137 {
138 pbucket->plinkLast->SetNext(plinkBlock);
139 pbucket->plinkLast = plinkBlock;
140 }
141 else
142 {
143 pbucket->plinkFirst = pbucket->plinkLast = plinkBlock;
144 }
145 plinkBlock->SetNext(nullptr);
146 }
147
148 m_uiSortedBlocks++;
149
150 if (0)
151 {
152 printf("%u: e=%.3f\n", uiLink, fBlockError);
153 Print();
154 printf("\n\n\n");
155 }
156 }
157 //printf("num blocks already done: %d\n",numDone);
158 //link the blocks together across buckets
159 m_plinkFirst = nullptr;
160 m_plinkLast = nullptr;
161 for (int iBucket = m_iBuckets - 1; iBucket >= 0; iBucket--)
162 {
163 Bucket *pbucket = &m_pabucket[iBucket];
164
165 if (pbucket->plinkFirst)
166 {
167 if (m_plinkFirst == nullptr)
168 {
169 m_plinkFirst = pbucket->plinkFirst;
170 }
171 else
172 {
173 assert(pbucket->plinkLast->GetNext() == nullptr);
174 m_plinkLast->SetNext(pbucket->plinkFirst);
175 }
176
177 m_plinkLast = pbucket->plinkLast;
178 }
179 }
180
181
182 }
183
184 // ----------------------------------------------------------------------------------------------------
185 // clear all of the buckets. normally done in preparation for a sort
186 //
187 void SortedBlockList::InitBuckets(void)
188 {
189 for (int iBucket = 0; iBucket < m_iBuckets; iBucket++)
190 {
191 Bucket *pbucket = &m_pabucket[iBucket];
192
193 pbucket->plinkFirst = 0;
194 pbucket->plinkLast = 0;
195 }
196 }
197
198 // ----------------------------------------------------------------------------------------------------
199 // print out the list of sorted 4x4 blocks
200 // normally used for debugging
201 //
202 void SortedBlockList::Print(void)
203 {
204 for (int iBucket = m_iBuckets-1; iBucket >= 0; iBucket--)
205 {
206 Bucket *pbucket = &m_pabucket[iBucket];
207
208 unsigned int uiBlocks = 0;
209 for (Link *plink = pbucket->plinkFirst; plink != nullptr; plink = plink->GetNext() )
210 {
211 uiBlocks++;
212
213 if (plink == pbucket->plinkLast)
214 {
215 break;
216 }
217 }
218
219 float fBucketError = m_fMaxError * iBucket / m_iBuckets;
220 float fBucketRMS = sqrtf(fBucketError / (4.0f*16.0f) );
221 printf("%3d: e=%.3f rms=%.6f %u\n", iBucket, fBucketError, fBucketRMS, uiBlocks);
222 }
223 }
224
225 // ----------------------------------------------------------------------------------------------------
226 //
227
228 } // namespace Etc