| 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 |