190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* 2f71323e297a928af368937089d3ed71239786f86Andreas Huber * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber * 4f71323e297a928af368937089d3ed71239786f86Andreas Huber * Use of this source code is governed by a BSD-style license 5f71323e297a928af368937089d3ed71239786f86Andreas Huber * that can be found in the LICENSE file in the root of the source 6f71323e297a928af368937089d3ed71239786f86Andreas Huber * tree. An additional intellectual property rights grant can be found 7f71323e297a928af368937089d3ed71239786f86Andreas Huber * in the file PATENTS. All contributing project authors may 8f71323e297a928af368937089d3ed71239786f86Andreas Huber * be found in the AUTHORS file in the root of the source tree. 990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber */ 1090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* This code is in the public domain. 1390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** Version: 1.1 Author: Walt Karas 1490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 1590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#include "hmm_intrnl.h" 1790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 18ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuangvoid U(shrink_chunk)(U(descriptor) *desc, U(size_bau) n_baus_to_shrink) { 19ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang head_record *dummy_end_block = (head_record *) 20ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang BAUS_BACKWARD(desc->end_of_shrinkable_chunk, DUMMY_END_BLOCK_BAUS); 2190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef HMM_AUDIT_FAIL 2390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 24ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (dummy_end_block->block_size != 0) 25ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Chunk does not have valid dummy end block. */ 26ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang HMM_AUDIT_FAIL 2790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 2990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 30ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (n_baus_to_shrink) { 31ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang head_record *last_block = (head_record *) 32ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang BAUS_BACKWARD( 33ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang dummy_end_block, dummy_end_block->previous_block_size); 3490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 3590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef HMM_AUDIT_FAIL 36ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AUDIT_BLOCK(last_block) 3790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 3890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 39ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (last_block == desc->last_freed) { 40ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang U(size_bau) bs = BLOCK_BAUS(last_block); 41ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 42ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Chunk will not be shrunk out of existence if 43ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** 1. There is at least one allocated block in the chunk 44ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** and the amount to shrink is exactly the size of the 45ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** last block, OR 46ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** 2. After the last block is shrunk, there will be enough 47ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** BAUs left in it to form a minimal size block. */ 48ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang int chunk_will_survive = 49ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (PREV_BLOCK_BAUS(last_block) && (n_baus_to_shrink == bs)) || 50ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (n_baus_to_shrink <= (U(size_bau))(bs - MIN_BLOCK_BAUS)); 51ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 52ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (chunk_will_survive || 53ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (!PREV_BLOCK_BAUS(last_block) && 54ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (n_baus_to_shrink == 55ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (U(size_bau))(bs + DUMMY_END_BLOCK_BAUS)))) { 56ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang desc->last_freed = 0; 57ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 58ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (chunk_will_survive) { 59ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang bs -= n_baus_to_shrink; 60ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 61ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (bs) { 62ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* The last (non-dummy) block was not completely 63ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** eliminated by the shrink. */ 64ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 65ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang last_block->block_size = bs; 66ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang 67ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* Create new dummy end record. 68ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang */ 69ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang dummy_end_block = 70ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang (head_record *) BAUS_FORWARD(last_block, bs); 71ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang dummy_end_block->previous_block_size = bs; 72ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang dummy_end_block->block_size = 0; 7390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef HMM_AUDIT_FAIL 7590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 76ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang if (desc->avl_tree_root) 77ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root)) 7890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 7990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 80ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang U(into_free_collection)(desc, last_block); 81ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } else { 82ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang /* The last (non-dummy) block was completely 83ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** eliminated by the shrink. Make its head 84ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang ** the new dummy end block. 85ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang */ 86ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang last_block->block_size = 0; 87ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang last_block->previous_block_size &= ~HIGH_BIT_BAU_SIZE; 88ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 89ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 90ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 9190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef HMM_AUDIT_FAIL 93ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 94ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang HMM_AUDIT_FAIL 9590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 96ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 9790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 9890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef HMM_AUDIT_FAIL 99ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang else 100ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang HMM_AUDIT_FAIL 10190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 102ba164dffc5a6795bce97fae02b51ccf3330e15e4hkuang } 10390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 104