1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

use crate::utils::assert_fast;
use std::alloc;
use std::alloc::Layout;
use std::cmp;
use std::mem;

const AGING_DIVISOR: u32 = 16;

pub struct HTable {
    pub table: Box<[[HTableEntry; 64]; 64]>,
    pub max: u32,
}

pub struct HTableEntry {
    pub data: u32,
}

impl HTable {
    /// Increases `[from][to]` history slot value based on `depth`.
    pub fn add(&mut self, from: usize, to: usize, depth: u8) {
        assert_fast!(from < 64);
        assert_fast!(to < 64);

        let entry = &mut self.table[from][to];
        let value = (depth as u32).pow(2);
        let updated_value = entry.data + value;
        self.max = cmp::max(self.max, updated_value);

        entry.data = updated_value;
    }

    /// Punishes `[from][to]` history slot value based on `depth`.
    pub fn punish(&mut self, from: usize, to: usize, depth: u8) {
        assert_fast!(from < 64);
        assert_fast!(to < 64);

        let entry = &mut self.table[from][to];
        let value = depth as u32;
        let updated_value = match value <= entry.data {
            true => entry.data - value,
            false => 0,
        };

        entry.data = updated_value;
    }

    /// Gets `[from][to]` history slot value, relative to `max`.
    pub fn get(&self, from: usize, to: usize, max: u8) -> u8 {
        assert_fast!(from < 64);
        assert_fast!(to < 64);
        assert_fast!(max > 0);
        assert_fast!(self.max > 0);

        (self.table[from][to].data * (max as u32)).div_ceil(self.max) as u8
    }

    /// Ages all values in the history table by dividing them by the [AGING_DIVISOR].
    pub fn age_values(&mut self) {
        for row in self.table.iter_mut() {
            for entry in row {
                entry.data = entry.data.div_ceil(AGING_DIVISOR);
            }
        }

        self.max = self.age_value(self.max);
    }

    /// Ages a single value by dividing value by the [AGING_DIVISOR].
    fn age_value(&self, value: u32) -> u32 {
        value.div_ceil(AGING_DIVISOR)
    }
}

impl Default for HTable {
    /// Constructs a default instance of [HTable] by allocating `64 * 64 * mem::size_of::<HTableEntry>()`
    /// boxed array with zeroed elements.
    fn default() -> Self {
        const SIZE: usize = mem::size_of::<HTableEntry>();
        unsafe {
            let ptr = alloc::alloc_zeroed(Layout::from_size_align(64 * 64 * SIZE, SIZE).unwrap());
            Self { table: Box::from_raw(ptr as *mut [[HTableEntry; 64]; 64]), max: 1 }
        }
    }
}