1474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* 2474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * 4474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * Use of this source code is governed by a BSD-style license 5474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * that can be found in the LICENSE file in the root of the source 6474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * tree. An additional intellectual property rights grant can be found 7474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * in the file PATENTS. All contributing project authors may 8474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org * be found in the AUTHORS file in the root of the source tree. 9474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org */ 10474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 11474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 12474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org/* This code is in the public domain. 13474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org** Version: 1.1 Author: Walt Karas 14474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org*/ 15474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 16474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#include "hmm_intrnl.h" 17474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 186fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.orgvoid U(shrink_chunk)(U(descriptor) *desc, U(size_bau) n_baus_to_shrink) { 196fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org head_record *dummy_end_block = (head_record *) 206fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org BAUS_BACKWARD(desc->end_of_shrinkable_chunk, DUMMY_END_BLOCK_BAUS); 21474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 22474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef HMM_AUDIT_FAIL 23474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 246fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (dummy_end_block->block_size != 0) 256fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Chunk does not have valid dummy end block. */ 266fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org HMM_AUDIT_FAIL 27474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 28474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 29474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 306fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (n_baus_to_shrink) { 316fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org head_record *last_block = (head_record *) 326fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org BAUS_BACKWARD( 336fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org dummy_end_block, dummy_end_block->previous_block_size); 34474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 35474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef HMM_AUDIT_FAIL 366fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AUDIT_BLOCK(last_block) 37474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 38474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 396fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (last_block == desc->last_freed) { 406fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org U(size_bau) bs = BLOCK_BAUS(last_block); 416fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 426fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Chunk will not be shrunk out of existence if 436fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** 1. There is at least one allocated block in the chunk 446fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** and the amount to shrink is exactly the size of the 456fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** last block, OR 466fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** 2. After the last block is shrunk, there will be enough 476fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** BAUs left in it to form a minimal size block. */ 486fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org int chunk_will_survive = 496fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (PREV_BLOCK_BAUS(last_block) && (n_baus_to_shrink == bs)) || 506fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (n_baus_to_shrink <= (U(size_bau))(bs - MIN_BLOCK_BAUS)); 516fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 526fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (chunk_will_survive || 536fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (!PREV_BLOCK_BAUS(last_block) && 546fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (n_baus_to_shrink == 556fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (U(size_bau))(bs + DUMMY_END_BLOCK_BAUS)))) { 566fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org desc->last_freed = 0; 576fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 586fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (chunk_will_survive) { 596fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org bs -= n_baus_to_shrink; 606fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 616fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (bs) { 626fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* The last (non-dummy) block was not completely 636fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** eliminated by the shrink. */ 646fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 656fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org last_block->block_size = bs; 666fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org 676fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* Create new dummy end record. 686fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org */ 696fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org dummy_end_block = 706fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org (head_record *) BAUS_FORWARD(last_block, bs); 716fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org dummy_end_block->previous_block_size = bs; 726fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org dummy_end_block->block_size = 0; 73474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 74474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef HMM_AUDIT_FAIL 75474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 766fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org if (desc->avl_tree_root) 776fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org AUDIT_BLOCK(PTR_REC_TO_HEAD(desc->avl_tree_root)) 78474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 79474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 806fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org U(into_free_collection)(desc, last_block); 816fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } else { 826fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org /* The last (non-dummy) block was completely 836fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** eliminated by the shrink. Make its head 846fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org ** the new dummy end block. 856fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org */ 866fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org last_block->block_size = 0; 876fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org last_block->previous_block_size &= ~HIGH_BIT_BAU_SIZE; 886fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 896fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 906fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 91474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 92474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef HMM_AUDIT_FAIL 936fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 946fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org HMM_AUDIT_FAIL 95474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 966fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 97474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org 98474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#ifdef HMM_AUDIT_FAIL 996fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org else 1006fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org HMM_AUDIT_FAIL 101474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org#endif 1026fefe538d859300e7febe78271828198c10f1b52fgalligan@chromium.org } 103474eb7536515fb785e925cc9375d22817c416851hclam@chromium.org} 104