[nihav.git] / nihav-game / src / codecs / q.rs

use nihav_core::frame::*;
use nihav_core::codecs::*;
use nihav_core::io::byteio::*;

#[derive(Clone,Copy,Debug,PartialEq)]
enum TileMode {
    Start,
    Fill,
    ShortPattern(u8, u8),
    LongPattern(u8, u8),
    Run,
    Reuse,
    FB,
    MV,
    Forward(u16),
    Backward(u16),
    Skip,
}

struct QVideoDecoder {
    info:       NACodecInfoRef,
    pal:        [u8; 768],
    frame:      Vec<u8>,
    w:          usize,
    h:          usize,
    tile_w:     usize,
    tile_h:     usize,
    tile_off:   Vec<usize>,
    mode:       u8,
    patterns:   [u16; 128],
    version:    u8,
}

macro_rules! copy_tile {
    ($self: expr, $doff: expr, $soff: expr) => {
        let mut doff = $doff;
        let mut soff = $soff;
        for _y in 0..$self.tile_h {
            for x in 0..$self.tile_w {
                $self.frame[doff + x] = $self.frame[soff + x];
            }
            doff += $self.w;
            soff += $self.w;
        }
    }
}

impl QVideoDecoder {
    fn new() -> Self {
        QVideoDecoder {
            info:       NACodecInfoRef::default(),
            pal:        [0; 768],
            frame:      Vec::new(),
            w:          0,
            h:          0,
            tile_off:   Vec::new(),
            mode:       0,
            tile_w:     0,
            tile_h:     0,
            patterns:   [0; 128],
            version:    0,
        }
    }

    fn decode_mode7_tile(dst: &mut [u8], stride: usize, br: &mut ByteReader) -> DecoderResult<()> {
        let op                          = br.peek_byte()?;
        if op < 0xF8 {
            for dline in dst.chunks_mut(stride).take(4) {
                                          br.read_buf(&mut dline[..4])?;
            }
        } else if op == 0xF8 || op == 0xFF {
                                          br.read_byte()?;
        } else {
                                          br.read_byte()?;
            let mut clr = [0; 8];
            let nclr = (op - 0xF6) as usize;
            if nclr <= 4 {
                let mut pattern         = br.read_u32le()?;
                                          br.read_buf(&mut clr[..nclr])?;
                for dline in dst.chunks_mut(stride).take(4) {
                    for el in dline[..4].iter_mut() {
                        *el = clr[(pattern & 3) as usize];
                        pattern >>= 2;
                    }
                }
            } else {
                let mut pattern         = br.read_u24le()?;
                let     pattern2        = br.read_u24le()?;
                                          br.read_buf(&mut clr[..nclr])?;
                for (y, dline) in dst.chunks_mut(stride).take(4).enumerate() {
                    for el in dline[..4].iter_mut() {
                        *el = clr[(pattern & 7) as usize];
                        pattern >>= 3;
                    }
                    if y == 1 {
                        pattern = pattern2;
                    }
                }
            }
        }
        Ok(())
    }

    fn decode_frame_v3(&mut self, br: &mut ByteReader, _ctype: u16) -> DecoderResult<()> {
        let mut titer = self.tile_off.iter().enumerate();
        let mut skip_mode = false;
        while let Some((tile_no, &tile_off)) = titer.next()  {
            let op                      = br.read_byte()?;
            if op < 0xF8 {
                let clr0 = op;
                let clr1                = br.read_byte()?;
                if clr0 == clr1 {
                    for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                        for el in dline[..self.tile_w].iter_mut() {
                            *el = clr0;
                        }
                    }
                } else {
                    let mut pattern     = br.read_u16le()?;
                    for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                        for el in dline[..self.tile_w].iter_mut() {
                            *el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
                            pattern <<= 1;
                        }
                    }
                }
            } else {
                match op {
                    0xF8 => {
                        unimplemented!();
                    },
                    0xF9 => {
                        let run         = br.read_byte()? as usize;
                        validate!(run > 0);

                        validate!(tile_no > 0);
                        let mut tile_off = tile_off;
                        for i in 0..run {
                            if !skip_mode {
                                copy_tile!(self, tile_off, self.tile_off[tile_no - 1]);
                            }
                            if i + 1 < run {
                                let (_tno, &toff) = titer.next().unwrap();
                                tile_off = toff;
                            }
                        }
                    },
                    0xFA => {
                        let off         = br.read_u16le()? as usize;
                        validate!(tile_no + off < self.tile_off.len());
                        copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
                    },
                    0xFB => {
                        let off         = br.read_u16le()? as usize;
                        validate!(off <= tile_no);
                        copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
                    },
                    0xFC => {
                        const MV_PART: [i8; 16] = [ 0, 4, 8, 12, 16, 20, 24, 28, -32, -4, -8, -12, -16, -20, -24, -28 ];

                        let idx         = br.read_byte()? as usize;
                        let x = MV_PART[(idx & 0xF) as usize] as isize;
                        let y = MV_PART[(idx >>  4) as usize] as isize;
                        let src_off = (tile_off as isize) + x + y * (self.w as isize);
                        validate!(src_off >= 0);
                        validate!((src_off as usize) + self.tile_w + (self.tile_h - 1) * self.w <= self.w * self.h);

                        copy_tile!(self, tile_off, src_off as usize);
                    },
                    0xFD => {
                        let off         = (br.read_byte()? as usize) + 1;
                        validate!(tile_no + off < self.tile_off.len());
                        copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
                    },
                    0xFE => {
                        let off         = (br.read_byte()? as usize) + 1;
                        validate!(off <= tile_no);
                        copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
                    },
                    _ => {},
                };
            }
            skip_mode = op == 0xFF;
        }

        Ok(())
    }

    fn decode_frame(&mut self, br: &mut ByteReader, _ctype: u16) -> DecoderResult<()> {
        let mut titer = self.tile_off.iter().enumerate();
        let mut last_mode = TileMode::Start;

        while let Some((tile_no, &tile_off)) = titer.next()  {
            let op                      = br.read_byte()?;
            if op < 0xF8 {
                let clr0 = op;
                let clr1                = br.read_byte()?;
                if clr0 == clr1 {
                    for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                        for el in dline[..self.tile_w].iter_mut() {
                            *el = clr0;
                        }
                    }
                    last_mode = TileMode::Fill;
                } else {
                    let pat             = br.read_byte()?;
                    let mut pattern = if pat < 128 {
                            last_mode = TileMode::ShortPattern(clr0, clr1);
                            self.patterns[pat as usize]
                        } else {
                            last_mode = TileMode::LongPattern(clr0, clr1);
                            u16::from(pat) | (u16::from(br.read_byte()?) << 8)
                        };
                    for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                        for el in dline[..self.tile_w].iter_mut() {
                            *el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
                            pattern <<= 1;
                        }
                    }
                }
            } else {
                match op {
                    0xF8 => {
                        unimplemented!();
                    },
                    0xF9 => {
                        let run         = br.read_byte()? as usize;
                        validate!(run > 0);

                        validate!(tile_no > 0);
                        validate!(last_mode != TileMode::Start);
                        let mut tile_no  = tile_no;
                        let mut tile_off = tile_off;
                        for i in 0..run {
                            let copy_off = match last_mode {
                                    TileMode::Forward(off) => {
                                        tile_no + (off as usize)
                                    },
                                    TileMode::Backward(off) => {
                                        validate!(tile_no >= (off as usize));
                                        tile_no - (off as usize)
                                    },
                                    TileMode::Skip => self.tile_off.len(),
                                    _ => tile_no - 1,
                                };
                            if copy_off < self.tile_off.len() {
                                copy_tile!(self, tile_off, self.tile_off[copy_off]);
                            }
                            if i + 1 < run {
                                let (tno, &toff) = titer.next().unwrap();
                                tile_no  = tno;
                                tile_off = toff;
                            }
                        }
                        last_mode = TileMode::Run;
                    },
                    0xFA => {
                        let rtile       = br.read_u16le()? as usize;
                        validate!(rtile < self.tile_off.len());
                        copy_tile!(self, tile_off, self.tile_off[rtile]);
                        last_mode = TileMode::Reuse;
                    },
                    0xFB => {
                        match self.mode {
                            6 => {
                                let run = br.read_byte()? as usize;
                                validate!(run >= 2);
                                let mut tile_no  = tile_no;
                                let mut tile_off = tile_off;
                                for i in 0..run {
                                    match last_mode {
                                        TileMode::Start => return Err(DecoderError::InvalidData),
                                        TileMode::Fill => {
                                            let clr = br.read_byte()?;
                                            for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                                                for el in dline[..self.tile_w].iter_mut() {
                                                    *el = clr;
                                                }
                                            }
                                        },
                                        TileMode::ShortPattern(clr0, clr1) => {
                                            let pat = br.read_byte()?;
                                            let mut pattern = if pat < 128 {
                                                    self.patterns[pat as usize]
                                                } else {
                                                    u16::from(pat) | (u16::from(br.read_byte()?) << 8)
                                                };
                                            for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                                                for el in dline[..self.tile_w].iter_mut() {
                                                    *el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
                                                    pattern <<= 1;
                                                }
                                            }
                                        },
                                        TileMode::LongPattern(clr0, clr1) => {
                                            let mut pattern = br.read_u16le()?;
                                            for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
                                                for el in dline[..self.tile_w].iter_mut() {
                                                    *el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
                                                    pattern <<= 1;
                                                }
                                            }
                                        },
                                        TileMode::Reuse => {
                                            let rtile       = br.read_u16le()? as usize;
                                            validate!(rtile < self.tile_off.len());
                                            copy_tile!(self, tile_off, self.tile_off[rtile]);
                                        },
                                        TileMode::MV => {
                                            let idx         = br.read_byte()? as usize;
                                            let (x, y) = DEF_MVS[idx];
                                            let src_off = (tile_off as isize) + (x as isize) * 4 + (y as isize) * 4 * (self.w as isize);
                                            validate!(src_off >= 0);
                                            validate!((src_off as usize) + self.tile_w + (self.tile_h - 1) * self.w <= self.w * self.h);
                                            copy_tile!(self, tile_off, src_off as usize);
                                        },
                                        TileMode::Forward(_) => {
                                            let off         = (br.read_byte()? as usize) + 1;
                                            validate!(tile_no + off < self.tile_off.len());
                                            copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
                                        },
                                        TileMode::Backward(_) => {
                                            let off         = (br.read_byte()? as usize) + 1;
                                            validate!(off <= tile_no);
                                            copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
                                        },
                                        _ => unimplemented!(),
                                    };

                                    if i + 1 < run {
                                        let (tno, &toff) = titer.next().unwrap();
                                        tile_no  = tno;
                                        tile_off = toff;
                                    }
                                }
                            },
                            7 => {
                                validate!(self.tile_w == 4 && self.tile_h == 4);
                                let run = br.read_byte()? as usize;
                                validate!(run > 0);

                                let mut tile_off = tile_off;
                                for i in 0..run {
                                    Self::decode_mode7_tile(&mut self.frame[tile_off..], self.w, br)?;

                                    if i + 1 < run {
                                        let (_tno, &toff) = titer.next().unwrap();
                                        tile_off = toff;
                                    }
                                }
                            },
                            _ => {
                                unimplemented!();
                            },
                        };
                        last_mode = TileMode::FB;
                    },
                    0xFC => {
                        let idx         = br.read_byte()? as usize;
                        let (x, y) = DEF_MVS[idx];
                        let src_off = (tile_off as isize) + (x as isize) * 4 + (y as isize) * 4 * (self.w as isize);
                        validate!(src_off >= 0);
                        validate!((src_off as usize) + self.tile_w + (self.tile_h - 1) * self.w <= self.w * self.h);

                        copy_tile!(self, tile_off, src_off as usize);
                        last_mode = TileMode::MV;
                    },
                    0xFD => {
                        let off         = (br.read_byte()? as usize) + 1;
                        validate!(tile_no + off < self.tile_off.len());
                        copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
                        last_mode = TileMode::Forward(off as u16);
                    },
                    0xFE => {
                        let off         = (br.read_byte()? as usize) + 1;
                        validate!(off <= tile_no);
                        copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
                        last_mode = TileMode::Backward(off as u16);
                    },
                    _ => {
                        last_mode = TileMode::Skip;
                    },
                };
            }
        }

        Ok(())
    }

    fn output_frame(&mut self, bufinfo: &mut NABufferType, w: usize, h: usize) {
        let bufo = bufinfo.get_vbuf();
        let mut buf = bufo.unwrap();
        let paloff = buf.get_offset(1);
        let stride = buf.get_stride(0);
        let data = buf.get_data_mut().unwrap();
        let dst = data.as_mut_slice();

        dst[paloff..][..768].copy_from_slice(&self.pal);
        for (dline, sline) in dst.chunks_mut(stride).zip(self.frame.chunks(w)).take(h) {
            dline[..w].copy_from_slice(sline);
        }
    }
}

impl NADecoder for QVideoDecoder {
    fn init(&mut self, _supp: &mut NADecoderSupport, info: NACodecInfoRef) -> DecoderResult<()> {
        if let NACodecTypeInfo::Video(_vinfo) = info.get_properties() {
            let mut w;
            let mut h;
            if let Some(buf) = info.get_extradata() {
                validate!(buf.len() >= 22);
                w = read_u16le(&buf[4..])? as usize;
                h = read_u16le(&buf[6..])? as usize;
                self.tile_w = buf[8] as usize;
                self.tile_h = buf[9] as usize;
                validate!(self.tile_w > 0 && self.tile_h > 0);
                if self.tile_w != 4 || self.tile_h != 4 {
                    return Err(DecoderError::NotImplemented);
                }
                self.version = buf[2];
                if self.version != 3{
                    w *= self.tile_w;
                    h *= self.tile_h;
                } else {
                    validate!((w % self.tile_w) == 0);
                    validate!((h % self.tile_h) == 0);
                }
            } else {
                return Err(DecoderError::InvalidData);
            }
            let myinfo = NACodecTypeInfo::Video(NAVideoInfo::new(w, h, false, PAL8_FORMAT));
            self.info = NACodecInfo::new_ref(info.get_name(), myinfo, info.get_extradata()).into_ref();
            self.w = w;
            self.h = h;

            self.mode = match self.version {
                    4 => 6,
                    5 => 7,
                    _ => 0,
                };

            self.frame.resize(w * h, 0);
            self.pal = [0; 768];
            self.tile_off = Vec::with_capacity((w / self.tile_w) * (h / self.tile_h));
            let mut off = 0;
            for _y in (0..h).step_by(self.tile_h) {
                for x in (0..w).step_by(self.tile_w) {
                    self.tile_off.push(off + x);
                }
                off += w * self.tile_h;
            }
            Ok(())
        } else {
            Err(DecoderError::InvalidData)
        }
    }
    fn decode(&mut self, _supp: &mut NADecoderSupport, pkt: &NAPacket) -> DecoderResult<NAFrameRef> {
        let src = pkt.get_buffer();
        validate!(!src.is_empty());

        let mut mr = MemoryReader::new_read(&src);
        let mut br = ByteReader::new(&mut mr);

        while br.left() >= 6 {
            let ctype                   = br.read_u16le()?;
            let csize                   = br.read_u32le()? as usize;
            validate!(csize <= (br.left() as usize));
            match ctype {
                1 => {
                    validate!(csize <= 768);
                                          br.read_buf(&mut self.pal[..csize])?;
                    for el in self.pal[..csize].iter_mut() {
                        *el = (*el << 2) | (*el >> 4);
                    }
                },
                2 | 3 | 4 | 9 | 11 => {
                    if self.version == 5 {
                        self.mode = if ctype == 9 || ctype == 11 { 7 } else { 6 };
                    }
                    if self.version == 3 {
                        self.decode_frame_v3(&mut br, ctype)?;
                    } else {
                        self.decode_frame(&mut br, ctype)?;
                    }
                },
                5 => {
                    validate!(csize <= 256 && (csize & 1) == 0);
                    for el in self.patterns[..csize/2].iter_mut() {
                        *el             = br.read_u16le()?;
                    }
                },
                6 | 7 => {
                    self.mode = ctype as u8;
                },
                _ => return Err(DecoderError::InvalidData),
            };
        }

        let mut bufinfo = alloc_video_buffer(self.info.get_properties().get_video_info().unwrap(), 0)?;

        self.output_frame(&mut bufinfo, self.w, self.h);

        let mut frm = NAFrame::new_from_pkt(pkt, self.info.clone(), bufinfo);
        frm.set_frame_type(if pkt.is_keyframe() { FrameType::I } else { FrameType::P });
        Ok(frm.into_ref())
    }
    fn flush(&mut self) {
    }
}

impl NAOptionHandler for QVideoDecoder {
    fn get_supported_options(&self) -> &[NAOptionDefinition] { &[] }
    fn set_options(&mut self, _options: &[NAOption]) { }
    fn query_option_value(&self, _name: &str) -> Option<NAValue> { None }
}

pub fn get_decoder() -> Box<dyn NADecoder + Send> {
    Box::new(QVideoDecoder::new())
}

#[cfg(test)]
mod test {
    use nihav_core::codecs::RegisteredDecoders;
    use nihav_core::demuxers::RegisteredDemuxers;
    use nihav_codec_support::test::dec_video::*;
    use crate::game_register_all_decoders;
    use crate::game_register_all_demuxers;

    // samples from Deathgate, Mission Critical and Shannara games
    #[test]
    fn test_q_video3() {
        let mut dmx_reg = RegisteredDemuxers::new();
        game_register_all_demuxers(&mut dmx_reg);
        let mut dec_reg = RegisteredDecoders::new();
        game_register_all_decoders(&mut dec_reg);

        test_decoding("legend-q", "legend-q-video", "assets/Game/dgate101.q", Some(31), &dmx_reg, &dec_reg,
                      ExpectedTestResult::MD5([0x9cc0014c, 0xf6332802, 0xfabeb715, 0xdfaa11c0]));
    }
    #[test]
    fn test_q_video4() {
        let mut dmx_reg = RegisteredDemuxers::new();
        game_register_all_demuxers(&mut dmx_reg);
        let mut dec_reg = RegisteredDecoders::new();
        game_register_all_decoders(&mut dec_reg);

        test_decoding("legend-q", "legend-q-video", "assets/Game/1925.Q", None, &dmx_reg, &dec_reg,
                      ExpectedTestResult::MD5([0xe1af971a, 0xfb509816, 0x9d60f5d6, 0xbcf48a3b]));
    }
    #[test]
    fn test_q_video5() {
        let mut dmx_reg = RegisteredDemuxers::new();
        game_register_all_demuxers(&mut dmx_reg);
        let mut dec_reg = RegisteredDecoders::new();
        game_register_all_decoders(&mut dec_reg);

        test_decoding("legend-q", "legend-q-video", "assets/Game/mc703.q", Some(16), &dmx_reg, &dec_reg,
                      ExpectedTestResult::MD5([0xf65ea3ce, 0x3052b2bb, 0xb10f8f69, 0x530d60f9]));
    }
}

const DEF_MVS: [(i8, i8); 256] = [
    ( 0, 8), ( 1, 8), ( 2, 8), ( 3, 8), ( 4, 8), ( 5, 8), ( 6, 8), ( 7, 8),
    (-8, 8), (-1, 8), (-2, 8), (-3, 8), (-4, 8), (-5, 8), (-6, 8), (-7, 8),
    ( 0, 9), ( 1, 9), ( 2, 9), ( 3, 9), ( 4, 9), ( 5, 9), ( 6, 9), ( 7, 9),
    (-8, 9), (-1, 9), (-2, 9), (-3, 9), (-4, 9), (-5, 9), (-6, 9), (-7, 9),
    ( 0, 2), ( 1, 2), ( 2, 2), ( 3, 2), ( 4, 2), ( 5, 2), ( 6, 2), ( 7, 2),
    (-8, 2), (-1, 2), (-2, 2), (-3, 2), (-4, 2), (-5, 2), (-6, 2), (-7, 2),
    ( 0, 3), ( 1, 3), ( 2, 3), ( 3, 3), ( 4, 3), ( 5, 3), ( 6, 3), ( 7, 3),
    (-8, 3), (-1, 3), (-2, 3), (-3, 3), (-4, 3), (-5, 3), (-6, 3), (-7, 3),
    ( 0, 4), ( 1, 4), ( 2, 4), ( 3, 4), ( 4, 4), ( 5, 4), ( 6, 4), ( 7, 4),
    (-8, 4), (-1, 4), (-2, 4), (-3, 4), (-4, 4), (-5, 4), (-6, 4), (-7, 4),
    ( 0, 5), ( 1, 5), ( 2, 5), ( 3, 5), ( 4, 5), ( 5, 5), ( 6, 5), ( 7, 5),
    (-8, 5), (-1, 5), (-2, 5), (-3, 5), (-4, 5), (-5, 5), (-6, 5), (-7, 5),
    ( 0, 6), ( 1, 6), ( 2, 6), ( 3, 6), ( 4, 6), ( 5, 6), ( 6, 6), ( 7, 6),
    (-8, 6), (-1, 6), (-2, 6), (-3, 6), (-4, 6), (-5, 6), (-6, 6), (-7, 6),
    ( 0, 7), ( 1, 7), ( 2, 7), ( 3, 7), ( 4, 7), ( 5, 7), ( 6, 7), ( 7, 7),
    (-8, 7), (-1, 7), (-2, 7), (-3, 7), (-4, 7), (-5, 7), (-6, 7), (-7, 7),
    ( 0,-8), ( 1,-8), ( 2,-8), ( 3,-8), ( 4,-8), ( 5,-8), ( 6,-8), ( 7,-8),
    (-8,-8), (-1,-8), (-2,-8), (-3,-8), (-4,-8), (-5,-8), (-6,-8), (-7,-8),
    ( 0,-9), ( 1,-9), ( 2,-9), ( 3,-9), ( 4,-9), ( 5,-9), ( 6,-9), ( 7,-9),
    (-8,-9), (-1,-9), (-2,-9), (-3,-9), (-4,-9), (-5,-9), (-6,-9), (-7,-9),
    ( 0,-2), ( 1,-2), ( 2,-2), ( 3,-2), ( 4,-2), ( 5,-2), ( 6,-2), ( 7,-2),
    (-8,-2), (-1,-2), (-2,-2), (-3,-2), (-4,-2), (-5,-2), (-6,-2), (-7,-2),
    ( 0,-3), ( 1,-3), ( 2,-3), ( 3,-3), ( 4,-3), ( 5,-3), ( 6,-3), ( 7,-3),
    (-8,-3), (-1,-3), (-2,-3), (-3,-3), (-4,-3), (-5,-3), (-6,-3), (-7,-3),
    ( 0,-4), ( 1,-4), ( 2,-4), ( 3,-4), ( 4,-4), ( 5,-4), ( 6,-4), ( 7,-4),
    (-8,-4), (-1,-4), (-2,-4), (-3,-4), (-4,-4), (-5,-4), (-6,-4), (-7,-4),
    ( 0,-5), ( 1,-5), ( 2,-5), ( 3,-5), ( 4,-5), ( 5,-5), ( 6,-5), ( 7,-5),
    (-8,-5), (-1,-5), (-2,-5), (-3,-5), (-4,-5), (-5,-5), (-6,-5), (-7,-5),
    ( 0,-6), ( 1,-6), ( 2,-6), ( 3,-6), ( 4,-6), ( 5,-6), ( 6,-6), ( 7,-6),
    (-8,-6), (-1,-6), (-2,-6), (-3,-6), (-4,-6), (-5,-6), (-6,-6), (-7,-6),
    ( 0,-7), ( 1,-7), ( 2,-7), ( 3,-7), ( 4,-7), ( 5,-7), ( 6,-7), ( 7,-7),
    (-8,-7), (-1,-7), (-2,-7), (-3,-7), (-4,-7), (-5,-7), (-6,-7), (-7,-7)
];
Commit	Line	Data
afe1e5ba KS	1	use nihav_core::frame::*;
	2	use nihav_core::codecs::*;
	3	use nihav_core::io::byteio::*;
	4
	5	#[derive(Clone,Copy,Debug,PartialEq)]
	6	enum TileMode {
	7	Start,
	8	Fill,
	9	ShortPattern(u8, u8),
	10	LongPattern(u8, u8),
	11	Run,
	12	Reuse,
	13	FB,
	14	MV,
	15	Forward(u16),
	16	Backward(u16),
	17	Skip,
	18	}
	19
	20	struct QVideoDecoder {
	21	info: NACodecInfoRef,
	22	pal: [u8; 768],
	23	frame: Vec<u8>,
	24	w: usize,
	25	h: usize,
	26	tile_w: usize,
	27	tile_h: usize,
	28	tile_off: Vec<usize>,
	29	mode: u8,
	30	patterns: [u16; 128],
	31	version: u8,
	32	}
	33
	34	macro_rules! copy_tile {
	35	($self: expr, $doff: expr, $soff: expr) => {
	36	let mut doff = $doff;
	37	let mut soff = $soff;
	38	for _y in 0..$self.tile_h {
	39	for x in 0..$self.tile_w {
	40	$self.frame[doff + x] = $self.frame[soff + x];
	41	}
	42	doff += $self.w;
	43	soff += $self.w;
	44	}
	45	}
	46	}
	47
	48	impl QVideoDecoder {
	49	fn new() -> Self {
	50	QVideoDecoder {
	51	info: NACodecInfoRef::default(),
	52	pal: [0; 768],
	53	frame: Vec::new(),
	54	w: 0,
	55	h: 0,
	56	tile_off: Vec::new(),
	57	mode: 0,
	58	tile_w: 0,
	59	tile_h: 0,
	60	patterns: [0; 128],
	61	version: 0,
	62	}
	63	}
	64
65	fn decode_mode7_tile(dst: &mut [u8], stride: usize, br: &mut ByteReader) -> DecoderResult<()> {
66	let op = br.peek_byte()?;
67	if op < 0xF8 {
68	for dline in dst.chunks_mut(stride).take(4) {
69	br.read_buf(&mut dline[..4])?;
70	}
71	} else if op == 0xF8 \|\| op == 0xFF {
72	br.read_byte()?;
73	} else {
74	br.read_byte()?;
75	let mut clr = [0; 8];
76	let nclr = (op - 0xF6) as usize;
77	if nclr <= 4 {
78	let mut pattern = br.read_u32le()?;
79	br.read_buf(&mut clr[..nclr])?;
80	for dline in dst.chunks_mut(stride).take(4) {
81	for el in dline[..4].iter_mut() {
82	*el = clr[(pattern & 3) as usize];
83	pattern >>= 2;
84	}
85	}
86	} else {
87	let mut pattern = br.read_u24le()?;
88	let pattern2 = br.read_u24le()?;
89	br.read_buf(&mut clr[..nclr])?;
90	for (y, dline) in dst.chunks_mut(stride).take(4).enumerate() {
91	for el in dline[..4].iter_mut() {
92	*el = clr[(pattern & 7) as usize];
93	pattern >>= 3;
94	}
95	if y == 1 {
96	pattern = pattern2;
97	}
98	}
99	}
100	}
101	Ok(())
102	}
103
104	fn decode_frame_v3(&mut self, br: &mut ByteReader, _ctype: u16) -> DecoderResult<()> {
105	let mut titer = self.tile_off.iter().enumerate();
106	let mut skip_mode = false;
107	while let Some((tile_no, &tile_off)) = titer.next() {
108	let op = br.read_byte()?;
109	if op < 0xF8 {
110	let clr0 = op;
111	let clr1 = br.read_byte()?;
112	if clr0 == clr1 {
113	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
114	for el in dline[..self.tile_w].iter_mut() {
115	*el = clr0;
116	}
117	}
118	} else {
119	let mut pattern = br.read_u16le()?;
120	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
121	for el in dline[..self.tile_w].iter_mut() {
122	*el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
123	pattern <<= 1;
124	}
125	}
126	}
127	} else {
128	match op {
129	0xF8 => {
130	unimplemented!();
131	},
132	0xF9 => {
133	let run = br.read_byte()? as usize;
134	validate!(run > 0);
135
136	validate!(tile_no > 0);
137	let mut tile_off = tile_off;
138	for i in 0..run {
139	if !skip_mode {
140	copy_tile!(self, tile_off, self.tile_off[tile_no - 1]);
141	}
142	if i + 1 < run {
143	let (_tno, &toff) = titer.next().unwrap();
144	tile_off = toff;
145	}
146	}
147	},
148	0xFA => {
149	let off = br.read_u16le()? as usize;
150	validate!(tile_no + off < self.tile_off.len());
151	copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
152	},
153	0xFB => {
154	let off = br.read_u16le()? as usize;
155	validate!(off <= tile_no);
156	copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
157	},
158	0xFC => {
159	const MV_PART: [i8; 16] = [ 0, 4, 8, 12, 16, 20, 24, 28, -32, -4, -8, -12, -16, -20, -24, -28 ];
5181ac4d	160
afe1e5ba KS	161	let idx = br.read_byte()? as usize;
	162	let x = MV_PART[(idx & 0xF) as usize] as isize;
	163	let y = MV_PART[(idx >> 4) as usize] as isize;
	164	let src_off = (tile_off as isize) + x + y * (self.w as isize);
	165	validate!(src_off >= 0);
	166	validate!((src_off as usize) + self.tile_w + (self.tile_h - 1) * self.w <= self.w * self.h);
	167
	168	copy_tile!(self, tile_off, src_off as usize);
	169	},
	170	0xFD => {
	171	let off = (br.read_byte()? as usize) + 1;
	172	validate!(tile_no + off < self.tile_off.len());
	173	copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
	174	},
	175	0xFE => {
	176	let off = (br.read_byte()? as usize) + 1;
	177	validate!(off <= tile_no);
	178	copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
	179	},
	180	_ => {},
	181	};
	182	}
	183	skip_mode = op == 0xFF;
	184	}
	185
	186	Ok(())
	187	}
	188
	189	fn decode_frame(&mut self, br: &mut ByteReader, _ctype: u16) -> DecoderResult<()> {
	190	let mut titer = self.tile_off.iter().enumerate();
	191	let mut last_mode = TileMode::Start;
	192
	193	while let Some((tile_no, &tile_off)) = titer.next() {
	194	let op = br.read_byte()?;
	195	if op < 0xF8 {
	196	let clr0 = op;
	197	let clr1 = br.read_byte()?;
	198	if clr0 == clr1 {
	199	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
	200	for el in dline[..self.tile_w].iter_mut() {
	201	*el = clr0;
	202	}
	203	}
	204	last_mode = TileMode::Fill;
	205	} else {
	206	let pat = br.read_byte()?;
	207	let mut pattern = if pat < 128 {
	208	last_mode = TileMode::ShortPattern(clr0, clr1);
	209	self.patterns[pat as usize]
	210	} else {
	211	last_mode = TileMode::LongPattern(clr0, clr1);
	212	u16::from(pat) \| (u16::from(br.read_byte()?) << 8)
	213	};
	214	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
	215	for el in dline[..self.tile_w].iter_mut() {
	216	*el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
	217	pattern <<= 1;
	218	}
	219	}
	220	}
	221	} else {
	222	match op {
	223	0xF8 => {
	224	unimplemented!();
225	},
226	0xF9 => {
227	let run = br.read_byte()? as usize;
228	validate!(run > 0);
229
230	validate!(tile_no > 0);
231	validate!(last_mode != TileMode::Start);
232	let mut tile_no = tile_no;
233	let mut tile_off = tile_off;
234	for i in 0..run {
235	let copy_off = match last_mode {
236	TileMode::Forward(off) => {
237	tile_no + (off as usize)
238	},
239	TileMode::Backward(off) => {
240	validate!(tile_no >= (off as usize));
241	tile_no - (off as usize)
242	},
243	TileMode::Skip => self.tile_off.len(),
244	_ => tile_no - 1,
245	};
246	if copy_off < self.tile_off.len() {
247	copy_tile!(self, tile_off, self.tile_off[copy_off]);
248	}
249	if i + 1 < run {
250	let (tno, &toff) = titer.next().unwrap();
251	tile_no = tno;
252	tile_off = toff;
253	}
254	}
255	last_mode = TileMode::Run;
256	},
257	0xFA => {
258	let rtile = br.read_u16le()? as usize;
259	validate!(rtile < self.tile_off.len());
260	copy_tile!(self, tile_off, self.tile_off[rtile]);
261	last_mode = TileMode::Reuse;
262	},
263	0xFB => {
264	match self.mode {
265	6 => {
266	let run = br.read_byte()? as usize;
267	validate!(run >= 2);
268	let mut tile_no = tile_no;
269	let mut tile_off = tile_off;
270	for i in 0..run {
271	match last_mode {
272	TileMode::Start => return Err(DecoderError::InvalidData),
273	TileMode::Fill => {
274	let clr = br.read_byte()?;
275	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
276	for el in dline[..self.tile_w].iter_mut() {
277	*el = clr;
278	}
279	}
280	},
281	TileMode::ShortPattern(clr0, clr1) => {
282	let pat = br.read_byte()?;
283	let mut pattern = if pat < 128 {
284	self.patterns[pat as usize]
285	} else {
286	u16::from(pat) \| (u16::from(br.read_byte()?) << 8)
287	};
288	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
289	for el in dline[..self.tile_w].iter_mut() {
290	*el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
291	pattern <<= 1;
292	}
293	}
294	},
295	TileMode::LongPattern(clr0, clr1) => {
296	let mut pattern = br.read_u16le()?;
297	for dline in self.frame[tile_off..].chunks_mut(self.w).take(self.tile_h) {
298	for el in dline[..self.tile_w].iter_mut() {
299	*el = if (pattern & 0x8000) == 0 { clr0 } else { clr1 };
300	pattern <<= 1;
301	}
302	}
303	},
304	TileMode::Reuse => {
305	let rtile = br.read_u16le()? as usize;
306	validate!(rtile < self.tile_off.len());
307	copy_tile!(self, tile_off, self.tile_off[rtile]);
308	},
309	TileMode::MV => {
310	let idx = br.read_byte()? as usize;
311	let (x, y) = DEF_MVS[idx];
312	let src_off = (tile_off as isize) + (x as isize) * 4 + (y as isize) * 4 * (self.w as isize);
313	validate!(src_off >= 0);
314	validate!((src_off as usize) + self.tile_w + (self.tile_h - 1) * self.w <= self.w * self.h);
315	copy_tile!(self, tile_off, src_off as usize);
316	},
317	TileMode::Forward(_) => {
318	let off = (br.read_byte()? as usize) + 1;
319	validate!(tile_no + off < self.tile_off.len());
320	copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
321	},
322	TileMode::Backward(_) => {
323	let off = (br.read_byte()? as usize) + 1;
324	validate!(off <= tile_no);
325	copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
326	},
327	_ => unimplemented!(),
328	};
329
330	if i + 1 < run {
331	let (tno, &toff) = titer.next().unwrap();
332	tile_no = tno;
333	tile_off = toff;
334	}
335	}
336	},
337	7 => {
338	validate!(self.tile_w == 4 && self.tile_h == 4);
339	let run = br.read_byte()? as usize;
340	validate!(run > 0);
341
342	let mut tile_off = tile_off;
343	for i in 0..run {
344	Self::decode_mode7_tile(&mut self.frame[tile_off..], self.w, br)?;
345
346	if i + 1 < run {
347	let (_tno, &toff) = titer.next().unwrap();
348	tile_off = toff;
349	}
350	}
351	},
352	_ => {
353	unimplemented!();
354	},
355	};
356	last_mode = TileMode::FB;
357	},
358	0xFC => {
359	let idx = br.read_byte()? as usize;
360	let (x, y) = DEF_MVS[idx];
361	let src_off = (tile_off as isize) + (x as isize) * 4 + (y as isize) * 4 * (self.w as isize);
362	validate!(src_off >= 0);
363	validate!((src_off as usize) + self.tile_w + (self.tile_h - 1) * self.w <= self.w * self.h);
364
365	copy_tile!(self, tile_off, src_off as usize);
366	last_mode = TileMode::MV;
367	},
368	0xFD => {
369	let off = (br.read_byte()? as usize) + 1;
370	validate!(tile_no + off < self.tile_off.len());
371	copy_tile!(self, tile_off, self.tile_off[tile_no + off]);
372	last_mode = TileMode::Forward(off as u16);
373	},
374	0xFE => {
375	let off = (br.read_byte()? as usize) + 1;
376	validate!(off <= tile_no);
377	copy_tile!(self, tile_off, self.tile_off[tile_no - off]);
378	last_mode = TileMode::Backward(off as u16);
379	},
380	_ => {
381	last_mode = TileMode::Skip;
382	},
383	};
384	}
385	}
386
387	Ok(())
388	}
389
390	fn output_frame(&mut self, bufinfo: &mut NABufferType, w: usize, h: usize) {
391	let bufo = bufinfo.get_vbuf();
392	let mut buf = bufo.unwrap();
393	let paloff = buf.get_offset(1);
394	let stride = buf.get_stride(0);
395	let data = buf.get_data_mut().unwrap();
396	let dst = data.as_mut_slice();
397
398	dst[paloff..][..768].copy_from_slice(&self.pal);
399	for (dline, sline) in dst.chunks_mut(stride).zip(self.frame.chunks(w)).take(h) {
400	dline[..w].copy_from_slice(sline);
401	}
402	}
403	}
404
405	impl NADecoder for QVideoDecoder {
406	fn init(&mut self, _supp: &mut NADecoderSupport, info: NACodecInfoRef) -> DecoderResult<()> {
407	if let NACodecTypeInfo::Video(_vinfo) = info.get_properties() {
408	let mut w;
409	let mut h;
410	if let Some(buf) = info.get_extradata() {
411	validate!(buf.len() >= 22);
412	w = read_u16le(&buf[4..])? as usize;
413	h = read_u16le(&buf[6..])? as usize;
414	self.tile_w = buf[8] as usize;
415	self.tile_h = buf[9] as usize;
416	validate!(self.tile_w > 0 && self.tile_h > 0);
417	if self.tile_w != 4 \|\| self.tile_h != 4 {
418	return Err(DecoderError::NotImplemented);
419	}
420	self.version = buf[2];
421	if self.version != 3{
422	w *= self.tile_w;
423	h *= self.tile_h;
424	} else {
425	validate!((w % self.tile_w) == 0);
426	validate!((h % self.tile_h) == 0);
427	}
428	} else {
429	return Err(DecoderError::InvalidData);
430	}
431	let myinfo = NACodecTypeInfo::Video(NAVideoInfo::new(w, h, false, PAL8_FORMAT));
432	self.info = NACodecInfo::new_ref(info.get_name(), myinfo, info.get_extradata()).into_ref();
433	self.w = w;
434	self.h = h;
435
436	self.mode = match self.version {
437	4 => 6,
438	5 => 7,
439	_ => 0,
440	};
441
442	self.frame.resize(w * h, 0);
443	self.pal = [0; 768];
444	self.tile_off = Vec::with_capacity((w / self.tile_w) * (h / self.tile_h));
445	let mut off = 0;
446	for _y in (0..h).step_by(self.tile_h) {
447	for x in (0..w).step_by(self.tile_w) {
448	self.tile_off.push(off + x);
449	}
450	off += w * self.tile_h;
451	}
452	Ok(())
453	} else {
454	Err(DecoderError::InvalidData)
455	}
456	}
457	fn decode(&mut self, _supp: &mut NADecoderSupport, pkt: &NAPacket) -> DecoderResult<NAFrameRef> {
458	let src = pkt.get_buffer();
459	validate!(!src.is_empty());
460
461	let mut mr = MemoryReader::new_read(&src);
462	let mut br = ByteReader::new(&mut mr);
463
464	while br.left() >= 6 {
465	let ctype = br.read_u16le()?;
466	let csize = br.read_u32le()? as usize;
467	validate!(csize <= (br.left() as usize));
468	match ctype {
469	1 => {
470	validate!(csize <= 768);
471	br.read_buf(&mut self.pal[..csize])?;
472	for el in self.pal[..csize].iter_mut() {
473	el = (el << 2) \| (*el >> 4);
474	}
475	},
476	2 \| 3 \| 4 \| 9 \| 11 => {
477	if self.version == 5 {
478	self.mode = if ctype == 9 \|\| ctype == 11 { 7 } else { 6 };
479	}
480	if self.version == 3 {
481	self.decode_frame_v3(&mut br, ctype)?;
482	} else {
483	self.decode_frame(&mut br, ctype)?;
484	}
485	},
486	5 => {
487	validate!(csize <= 256 && (csize & 1) == 0);
488	for el in self.patterns[..csize/2].iter_mut() {
489	*el = br.read_u16le()?;
490	}
491	},
492	6 \| 7 => {
493	self.mode = ctype as u8;
494	},
495	_ => return Err(DecoderError::InvalidData),
496	};
497	}
498
499	let mut bufinfo = alloc_video_buffer(self.info.get_properties().get_video_info().unwrap(), 0)?;
500
501	self.output_frame(&mut bufinfo, self.w, self.h);
502
503	let mut frm = NAFrame::new_from_pkt(pkt, self.info.clone(), bufinfo);
504	frm.set_frame_type(if pkt.is_keyframe() { FrameType::I } else { FrameType::P });
505	Ok(frm.into_ref())
506	}
507	fn flush(&mut self) {
508	}
509	}
510
511	impl NAOptionHandler for QVideoDecoder {
512	fn get_supported_options(&self) -> &[NAOptionDefinition] { &[] }
513	fn set_options(&mut self, _options: &[NAOption]) { }
514	fn query_option_value(&self, _name: &str) -> Option<NAValue> { None }
515	}
516
517	pub fn get_decoder() -> Box<dyn NADecoder + Send> {
518	Box::new(QVideoDecoder::new())
519	}
520
521	#[cfg(test)]
522	mod test {
523	use nihav_core::codecs::RegisteredDecoders;
524	use nihav_core::demuxers::RegisteredDemuxers;
525	use nihav_codec_support::test::dec_video::*;
526	use crate::game_register_all_decoders;
527	use crate::game_register_all_demuxers;
528
886cde48	529	// samples from Deathgate, Mission Critical and Shannara games
afe1e5ba KS	530	#[test]
	531	fn test_q_video3() {
	532	let mut dmx_reg = RegisteredDemuxers::new();
	533	game_register_all_demuxers(&mut dmx_reg);
	534	let mut dec_reg = RegisteredDecoders::new();
	535	game_register_all_decoders(&mut dec_reg);
	536
	537	test_decoding("legend-q", "legend-q-video", "assets/Game/dgate101.q", Some(31), &dmx_reg, &dec_reg,
	538	ExpectedTestResult::MD5([0x9cc0014c, 0xf6332802, 0xfabeb715, 0xdfaa11c0]));
	539	}
	540	#[test]
	541	fn test_q_video4() {
	542	let mut dmx_reg = RegisteredDemuxers::new();
	543	game_register_all_demuxers(&mut dmx_reg);
	544	let mut dec_reg = RegisteredDecoders::new();
	545	game_register_all_decoders(&mut dec_reg);
	546
	547	test_decoding("legend-q", "legend-q-video", "assets/Game/1925.Q", None, &dmx_reg, &dec_reg,
	548	ExpectedTestResult::MD5([0xe1af971a, 0xfb509816, 0x9d60f5d6, 0xbcf48a3b]));
	549	}
	550	#[test]
	551	fn test_q_video5() {
	552	let mut dmx_reg = RegisteredDemuxers::new();
	553	game_register_all_demuxers(&mut dmx_reg);
	554	let mut dec_reg = RegisteredDecoders::new();
	555	game_register_all_decoders(&mut dec_reg);
	556
	557	test_decoding("legend-q", "legend-q-video", "assets/Game/mc703.q", Some(16), &dmx_reg, &dec_reg,
	558	ExpectedTestResult::MD5([0xf65ea3ce, 0x3052b2bb, 0xb10f8f69, 0x530d60f9]));
	559	}
	560	}
	561
	562	const DEF_MVS: [(i8, i8); 256] = [
	563	( 0, 8), ( 1, 8), ( 2, 8), ( 3, 8), ( 4, 8), ( 5, 8), ( 6, 8), ( 7, 8),
	564	(-8, 8), (-1, 8), (-2, 8), (-3, 8), (-4, 8), (-5, 8), (-6, 8), (-7, 8),
	565	( 0, 9), ( 1, 9), ( 2, 9), ( 3, 9), ( 4, 9), ( 5, 9), ( 6, 9), ( 7, 9),
	566	(-8, 9), (-1, 9), (-2, 9), (-3, 9), (-4, 9), (-5, 9), (-6, 9), (-7, 9),
	567	( 0, 2), ( 1, 2), ( 2, 2), ( 3, 2), ( 4, 2), ( 5, 2), ( 6, 2), ( 7, 2),
	568	(-8, 2), (-1, 2), (-2, 2), (-3, 2), (-4, 2), (-5, 2), (-6, 2), (-7, 2),
	569	( 0, 3), ( 1, 3), ( 2, 3), ( 3, 3), ( 4, 3), ( 5, 3), ( 6, 3), ( 7, 3),
	570	(-8, 3), (-1, 3), (-2, 3), (-3, 3), (-4, 3), (-5, 3), (-6, 3), (-7, 3),
	571	( 0, 4), ( 1, 4), ( 2, 4), ( 3, 4), ( 4, 4), ( 5, 4), ( 6, 4), ( 7, 4),
	572	(-8, 4), (-1, 4), (-2, 4), (-3, 4), (-4, 4), (-5, 4), (-6, 4), (-7, 4),
	573	( 0, 5), ( 1, 5), ( 2, 5), ( 3, 5), ( 4, 5), ( 5, 5), ( 6, 5), ( 7, 5),
	574	(-8, 5), (-1, 5), (-2, 5), (-3, 5), (-4, 5), (-5, 5), (-6, 5), (-7, 5),
	575	( 0, 6), ( 1, 6), ( 2, 6), ( 3, 6), ( 4, 6), ( 5, 6), ( 6, 6), ( 7, 6),
	576	(-8, 6), (-1, 6), (-2, 6), (-3, 6), (-4, 6), (-5, 6), (-6, 6), (-7, 6),
	577	( 0, 7), ( 1, 7), ( 2, 7), ( 3, 7), ( 4, 7), ( 5, 7), ( 6, 7), ( 7, 7),
	578	(-8, 7), (-1, 7), (-2, 7), (-3, 7), (-4, 7), (-5, 7), (-6, 7), (-7, 7),
	579	( 0,-8), ( 1,-8), ( 2,-8), ( 3,-8), ( 4,-8), ( 5,-8), ( 6,-8), ( 7,-8),
	580	(-8,-8), (-1,-8), (-2,-8), (-3,-8), (-4,-8), (-5,-8), (-6,-8), (-7,-8),
	581	( 0,-9), ( 1,-9), ( 2,-9), ( 3,-9), ( 4,-9), ( 5,-9), ( 6,-9), ( 7,-9),
	582	(-8,-9), (-1,-9), (-2,-9), (-3,-9), (-4,-9), (-5,-9), (-6,-9), (-7,-9),
	583	( 0,-2), ( 1,-2), ( 2,-2), ( 3,-2), ( 4,-2), ( 5,-2), ( 6,-2), ( 7,-2),
	584	(-8,-2), (-1,-2), (-2,-2), (-3,-2), (-4,-2), (-5,-2), (-6,-2), (-7,-2),
	585	( 0,-3), ( 1,-3), ( 2,-3), ( 3,-3), ( 4,-3), ( 5,-3), ( 6,-3), ( 7,-3),
	586	(-8,-3), (-1,-3), (-2,-3), (-3,-3), (-4,-3), (-5,-3), (-6,-3), (-7,-3),
	587	( 0,-4), ( 1,-4), ( 2,-4), ( 3,-4), ( 4,-4), ( 5,-4), ( 6,-4), ( 7,-4),
	588	(-8,-4), (-1,-4), (-2,-4), (-3,-4), (-4,-4), (-5,-4), (-6,-4), (-7,-4),
	589	( 0,-5), ( 1,-5), ( 2,-5), ( 3,-5), ( 4,-5), ( 5,-5), ( 6,-5), ( 7,-5),
	590	(-8,-5), (-1,-5), (-2,-5), (-3,-5), (-4,-5), (-5,-5), (-6,-5), (-7,-5),
	591	( 0,-6), ( 1,-6), ( 2,-6), ( 3,-6), ( 4,-6), ( 5,-6), ( 6,-6), ( 7,-6),
	592	(-8,-6), (-1,-6), (-2,-6), (-3,-6), (-4,-6), (-5,-6), (-6,-6), (-7,-6),
	593	( 0,-7), ( 1,-7), ( 2,-7), ( 3,-7), ( 4,-7), ( 5,-7), ( 6,-7), ( 7,-7),
594	(-8,-7), (-1,-7), (-2,-7), (-3,-7), (-4,-7), (-5,-7), (-6,-7), (-7,-7)
595	];