surpass/rasterizer/

pixel_segment.rs

// Copyright 2020 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

use std::cmp::Ordering;
use std::{fmt, mem};

use crate::{MAX_HEIGHT_SHIFT, MAX_WIDTH_SHIFT, PIXEL_WIDTH};

// Tile coordinates are signed integers stored with a bias.
// The value range goes from -1 to 2^bits - 2 inclusive.
const TILE_BIAS: i16 = 1;

pub const fn bit_field_lens<const TW: usize, const TH: usize>() -> [usize; 7] {
    const fn log2_round_up(n: usize) -> usize {
        if n.count_ones() == 1 {
            n.trailing_zeros() as usize
        } else {
            mem::size_of::<usize>() * 8 - n.leading_zeros() as usize
        }
    }

    let tile_width_shift = TW.trailing_zeros() as usize;
    let tile_height_shift = TH.trailing_zeros() as usize;

    let mut bit_field_lens = [
        MAX_HEIGHT_SHIFT - tile_height_shift,
        MAX_WIDTH_SHIFT - tile_width_shift,
        0,
        tile_width_shift,
        tile_height_shift,
        log2_round_up((PIXEL_WIDTH + 1) * 2),
        log2_round_up((PIXEL_WIDTH + 1) * 2),
    ];

    let layer_id_len = mem::size_of::<PixelSegment<TW, TH>>() * 8
        - bit_field_lens[0]
        - bit_field_lens[1]
        - bit_field_lens[3]
        - bit_field_lens[4]
        - bit_field_lens[5]
        - bit_field_lens[6];

    bit_field_lens[2] = layer_id_len;

    bit_field_lens
}

const fn shift_left_for<const TW: usize, const TH: usize>(bit_field_index: usize) -> u32 {
    let mut amount = 0;
    let mut i = 0;

    while i < bit_field_index {
        amount += bit_field_lens::<TW, TH>()[i];
        i += 1;
    }

    amount as u32
}

const fn shift_right_for<const TW: usize, const TH: usize>(bit_field_index: usize) -> u32 {
    (mem::size_of::<PixelSegment<TW, TH>>() * 8 - bit_field_lens::<TW, TH>()[bit_field_index])
        as u32
}

macro_rules! extract {
    ( $tw:expr , $th:expr , $pixel_segment:expr , $bit_field_index:expr ) => {{
        $pixel_segment << shift_left_for::<$tw, $th>($bit_field_index)
            >> shift_right_for::<$tw, $th>($bit_field_index)
    }};
}

#[derive(Clone, Copy, Default, Eq, Ord, PartialEq, PartialOrd)]
pub struct PixelSegment<const TW: usize, const TH: usize>(u64);

impl<const TW: usize, const TH: usize> PixelSegment<TW, TH> {
    const BIT_FIELD_LENGTH: [usize; 7] = bit_field_lens::<TW, TH>();

    #[inline]
    pub fn new(
        layer_id: u32,
        tile_x: i16,
        tile_y: i16,
        local_x: u8,
        local_y: u8,
        double_area_multiplier: u8,
        cover: i8,
    ) -> Self {
        let mut val = 0;

        val |= ((1 << Self::BIT_FIELD_LENGTH[0]) - 1) & (tile_y + TILE_BIAS).max(0) as u64;

        val <<= Self::BIT_FIELD_LENGTH[1];
        val |= ((1 << Self::BIT_FIELD_LENGTH[1]) - 1) as u64 & (tile_x + TILE_BIAS).max(0) as u64;

        val <<= Self::BIT_FIELD_LENGTH[2];
        val |= ((1 << Self::BIT_FIELD_LENGTH[2]) - 1) as u64 & u64::from(layer_id);

        val <<= Self::BIT_FIELD_LENGTH[3];
        val |= ((1 << Self::BIT_FIELD_LENGTH[3]) - 1) as u64 & u64::from(local_x);

        val <<= Self::BIT_FIELD_LENGTH[4];
        val |= ((1 << Self::BIT_FIELD_LENGTH[4]) - 1) as u64 & u64::from(local_y);

        val <<= Self::BIT_FIELD_LENGTH[5];
        val |= ((1 << Self::BIT_FIELD_LENGTH[5]) - 1) as u64 & u64::from(double_area_multiplier);

        val <<= Self::BIT_FIELD_LENGTH[6];
        val |= ((1 << Self::BIT_FIELD_LENGTH[6]) - 1) as u64 & cover as u64;

        Self(val)
    }

    #[inline]
    pub fn layer_id(self) -> u32 {
        extract!(TW, TH, self.0, 2) as u32
    }

    #[inline]
    pub fn tile_x(self) -> i16 {
        extract!(TW, TH, self.0, 1) as i16 - TILE_BIAS
    }

    #[inline]
    pub fn tile_y(self) -> i16 {
        extract!(TW, TH, self.0, 0) as i16 - TILE_BIAS
    }

    #[inline]
    pub fn local_x(self) -> u8 {
        extract!(TW, TH, self.0, 3) as u8
    }

    #[inline]
    pub fn local_y(self) -> u8 {
        extract!(TW, TH, self.0, 4) as u8
    }

    #[inline]
    fn double_area_multiplier(self) -> u8 {
        extract!(TW, TH, self.0, 5) as u8
    }

    #[inline]
    pub fn double_area(self) -> i16 {
        i16::from(self.double_area_multiplier()) * i16::from(self.cover())
    }

    #[inline]
    pub fn cover(self) -> i8 {
        extract!(TW, TH, self.0 as i64, 6) as i8
    }
}

impl<const TW: usize, const TH: usize> fmt::Debug for PixelSegment<TW, TH> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let unpacked: PixelSegmentUnpacked = (*self).into();
        f.debug_struct("PixelSegment")
            .field("layer_id", &unpacked.layer_id)
            .field("tile_x", &unpacked.tile_x)
            .field("tile_y", &unpacked.tile_y)
            .field("local_x", &unpacked.local_x)
            .field("local_y", &unpacked.local_y)
            .field("double_area", &unpacked.double_area)
            .field("cover", &unpacked.cover)
            .finish()
    }
}

impl<const TW: usize, const TH: usize> From<&PixelSegment<TW, TH>> for u64 {
    fn from(segment: &PixelSegment<TW, TH>) -> Self {
        segment.0
    }
}

#[inline]
pub fn search_last_by_key<F, K, const TW: usize, const TH: usize>(
    segments: &[PixelSegment<TW, TH>],
    key: K,
    mut f: F,
) -> Result<usize, usize>
where
    F: FnMut(&PixelSegment<TW, TH>) -> K,
    K: Ord,
{
    let mut len = segments.len();
    if len == 0 {
        return Err(0);
    }

    let mut start = 0;
    while len > 1 {
        let half = len / 2;
        let mid = start + half;
        (start, len) = match f(&segments[mid]).cmp(&key) {
            Ordering::Greater => (start, half),
            _ => (mid, len - half),
        };
    }

    match f(&segments[start]).cmp(&key) {
        Ordering::Less => Err(start + 1),
        Ordering::Equal => Ok(start),
        Ordering::Greater => Err(start),
    }
}

#[derive(Debug)]
pub struct PixelSegmentUnpacked {
    pub layer_id: u32,
    pub tile_x: i16,
    pub tile_y: i16,
    pub local_x: u8,
    pub local_y: u8,
    pub double_area: i16,
    pub cover: i8,
}

impl<const TW: usize, const TH: usize> From<PixelSegment<TW, TH>> for PixelSegmentUnpacked {
    fn from(value: PixelSegment<TW, TH>) -> Self {
        PixelSegmentUnpacked {
            layer_id: value.layer_id(),
            tile_x: value.tile_x(),
            tile_y: value.tile_y(),
            local_x: value.local_x(),
            local_y: value.local_y(),
            double_area: value.double_area(),
            cover: value.cover(),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    use crate::{LAYER_LIMIT, PIXEL_DOUBLE_WIDTH, TILE_HEIGHT, TILE_WIDTH};

    #[test]
    fn pixel_segment() {
        let layer_id = 3;
        let tile_x = 4;
        let tile_y = 5;
        let local_x = 6;
        let local_y = 7;
        let double_area_multiplier = 8;
        let cover = 9;

        let pixel_segment = PixelSegment::<TILE_WIDTH, TILE_HEIGHT>::new(
            layer_id,
            tile_x,
            tile_y,
            local_x,
            local_y,
            double_area_multiplier,
            cover,
        );

        assert_eq!(pixel_segment.layer_id(), layer_id);
        assert_eq!(pixel_segment.tile_x(), tile_x);
        assert_eq!(pixel_segment.tile_y(), tile_y);
        assert_eq!(pixel_segment.local_x(), local_x);
        assert_eq!(pixel_segment.local_y(), local_y);
        assert_eq!(
            pixel_segment.double_area(),
            i16::from(double_area_multiplier) * i16::from(cover)
        );
        assert_eq!(pixel_segment.cover(), cover);
    }

    #[test]
    fn pixel_segment_max() {
        let layer_id = LAYER_LIMIT as u32;
        let tile_x = (1 << (bit_field_lens::<TILE_WIDTH, TILE_HEIGHT>()[1] - 1)) - 1;
        let tile_y = (1 << (bit_field_lens::<TILE_WIDTH, TILE_HEIGHT>()[0] - 1)) - 1;
        let local_x = (1 << bit_field_lens::<TILE_WIDTH, TILE_HEIGHT>()[4]) - 1;
        let local_y = (1 << bit_field_lens::<TILE_WIDTH, TILE_HEIGHT>()[3]) - 1;
        let double_area_multiplier = PIXEL_DOUBLE_WIDTH as u8;
        let cover = PIXEL_WIDTH as i8;

        let pixel_segment = PixelSegment::<TILE_WIDTH, TILE_HEIGHT>::new(
            layer_id,
            tile_x,
            tile_y,
            local_x,
            local_y,
            double_area_multiplier,
            cover,
        );

        assert_eq!(pixel_segment.layer_id(), layer_id);
        assert_eq!(pixel_segment.tile_x(), tile_x);
        assert_eq!(pixel_segment.tile_y(), tile_y);
        assert_eq!(pixel_segment.local_x(), local_x);
        assert_eq!(pixel_segment.local_y(), local_y);
        assert_eq!(
            pixel_segment.double_area(),
            i16::from(double_area_multiplier) * i16::from(cover)
        );
        assert_eq!(pixel_segment.cover(), cover);
    }

    #[test]
    fn pixel_segment_min() {
        let layer_id = 0;
        let tile_x = -1;
        let tile_y = -1;
        let local_x = 0;
        let local_y = 0;
        let double_area_multiplier = 0;
        let cover = -(PIXEL_WIDTH as i8);

        let pixel_segment = PixelSegment::<TILE_WIDTH, TILE_HEIGHT>::new(
            layer_id,
            tile_x,
            tile_y,
            local_x,
            local_y,
            double_area_multiplier,
            cover,
        );

        assert_eq!(pixel_segment.layer_id(), layer_id);
        assert_eq!(pixel_segment.tile_x(), -1);
        assert_eq!(pixel_segment.tile_y(), -1);
        assert_eq!(pixel_segment.local_x(), local_x);
        assert_eq!(pixel_segment.local_y(), local_y);
        assert_eq!(
            pixel_segment.double_area(),
            i16::from(double_area_multiplier) * i16::from(cover)
        );
        assert_eq!(pixel_segment.cover(), cover);
    }

    #[test]
    fn pixel_segment_clipping() {
        let tile_x = -2;
        let tile_y = -2;

        let pixel_segment =
            PixelSegment::<TILE_WIDTH, TILE_HEIGHT>::new(0, tile_x, tile_y, 0, 0, 0, 0);

        assert_eq!(pixel_segment.tile_x(), -1, "negative tile coord clipped to -1");
        assert_eq!(pixel_segment.tile_y(), -1, "negative tile coord clipped to -1");

        let tile_x = i16::MIN;
        let tile_y = i16::MIN;

        let pixel_segment =
            PixelSegment::<TILE_WIDTH, TILE_HEIGHT>::new(0, tile_x, tile_y, 0, 0, 0, 0);

        assert_eq!(pixel_segment.tile_x(), -1, "negative tile coord clipped to -1");
        assert_eq!(pixel_segment.tile_y(), -1, "negative tile coord clipped to -1");
    }

    #[test]
    fn search_last_by_key_test() {
        let size = 50;
        let segments: Vec<_> = (0..(size * 2))
            .map(|i| PixelSegment::<TILE_WIDTH, TILE_HEIGHT>::new(i / 2, 0, 0, 0, 0, 0, 0))
            .collect();
        for i in 0..size {
            assert_eq!(
                Ok((i * 2 + 1) as usize),
                search_last_by_key(segments.as_slice(), i, |ps| ps.layer_id())
            );
        }
    }
}