Add Sixel support

Fixes #910

13 files changed, 1219 insertions, 3 deletions

diff --git a/alacritty_terminal/src/ansi.rs b/alacritty_terminal/src/ansi.rs
index 55492d36..7eb87910 100644
--- a/alacritty_terminal/src/ansi.rs
+++ b/alacritty_terminal/src/ansi.rs
@@ -10,6 +10,7 @@ use vte::{Params, ParamsIter};
 
 use alacritty_config_derive::ConfigDeserialize;
 
+use crate::graphics::{sixel, GraphicData};
 use crate::index::{Column, Line};
 use crate::term::color::Rgb;
 
@@ -136,6 +137,9 @@ enum Dcs {
 
     /// End of the synchronized update.
     SyncEnd,
+
+    /// Sixel data
+    SixelData(Box<sixel::Parser>),
 }
 
 /// The processor wraps a `vte::Parser` to ultimately call methods on a Handler.
@@ -240,6 +244,7 @@ impl Processor {
                     self.state.sync_state.timeout = Some(Instant::now() + SYNC_UPDATE_TIMEOUT);
                 },
                 Some(Dcs::SyncEnd) => self.stop_sync(handler),
+                Some(Dcs::SixelData(_)) => (),
                 None => (),
             },
         }
@@ -456,6 +461,14 @@ pub trait Handler {
 
     /// Report text area size in characters.
     fn text_area_size_chars(&mut self) {}
+
+    /// Create a parser for Sixel data.
+    fn start_sixel_graphic(&mut self, _params: &Params) -> Option<Box<sixel::Parser>> {
+        None
+    }
+
+    /// Insert a new graphic item.
+    fn insert_graphic(&mut self, _data: GraphicData, _palette: Option<Vec<Rgb>>) {}
 }
 
 /// Terminal cursor configuration.
@@ -529,6 +542,8 @@ pub enum Mode {
     LineFeedNewLine = 20,
     /// ?25
     ShowCursor = 25,
+    /// ?80
+    SixelScrolling = 80,
     /// ?1000
     ReportMouseClicks = 1000,
     /// ?1002
@@ -547,6 +562,8 @@ pub enum Mode {
     UrgencyHints = 1042,
     /// ?1049
     SwapScreenAndSetRestoreCursor = 1049,
+    /// Use a private palette for each new graphic.
+    SixelPrivateColorRegisters = 1070,
     /// ?2004
     BracketedPaste = 2004,
 }
@@ -568,6 +585,7 @@ impl Mode {
                 7 => Mode::LineWrap,
                 12 => Mode::BlinkingCursor,
                 25 => Mode::ShowCursor,
+                80 => Mode::SixelScrolling,
                 1000 => Mode::ReportMouseClicks,
                 1002 => Mode::ReportCellMouseMotion,
                 1003 => Mode::ReportAllMouseMotion,
@@ -577,6 +595,7 @@ impl Mode {
                 1007 => Mode::AlternateScroll,
                 1042 => Mode::UrgencyHints,
                 1049 => Mode::SwapScreenAndSetRestoreCursor,
+                1070 => Mode::SixelPrivateColorRegisters,
                 2004 => Mode::BracketedPaste,
                 _ => {
                     trace!("[unimplemented] primitive mode: {}", num);
@@ -908,6 +927,10 @@ where
                     self.state.dcs = Some(Dcs::SyncStart);
                 }
             },
+            ('q', []) => {
+                let parser = self.handler.start_sixel_graphic(params);
+                self.state.dcs = parser.map(Dcs::SixelData);
+            },
             _ => debug!(
                 "[unhandled hook] params={:?}, ints: {:?}, ignore: {:?}, action: {:?}",
                 params, intermediates, ignore, action
@@ -917,16 +940,29 @@ where
 
     #[inline]
     fn put(&mut self, byte: u8) {
-        debug!("[unhandled put] byte={:?}", byte);
+        match self.state.dcs {
+            Some(Dcs::SixelData(ref mut parser)) => {
+                if let Err(err) = parser.put(byte) {
+                    log::warn!("Failed to parse Sixel data: {}", err);
+                    self.state.dcs = None;
+                }
+            },
+
+            _ => debug!("[unhandled put] byte={:?}", byte),
+        }
     }
 
     #[inline]
     fn unhook(&mut self) {
-        match self.state.dcs {
+        match self.state.dcs.take() {
             Some(Dcs::SyncStart) => {
                 self.state.sync_state.timeout = Some(Instant::now() + SYNC_UPDATE_TIMEOUT);
             },
             Some(Dcs::SyncEnd) => (),
+            Some(Dcs::SixelData(parser)) => match parser.finish() {
+                Ok((graphic, palette)) => self.handler.insert_graphic(graphic, Some(palette)),
+                Err(err) => log::warn!("Failed to parse Sixel data: {}", err),
+            },
             _ => debug!("[unhandled unhook]"),
         }
     }
@@ -1235,6 +1271,7 @@ where
                 handler.set_scrolling_region(top, bottom);
             },
             ('S', []) => handler.scroll_up(next_param_or(1) as usize),
+            ('S', [b'?']) => handler.graphics_attribute(next_param_or(0), next_param_or(0)),
             ('s', []) => handler.save_cursor_position(),
             ('T', []) => handler.scroll_down(next_param_or(1) as usize),
             ('t', []) => match next_param_or(1) as usize {
diff --git a/alacritty_terminal/src/graphics/mod.rs b/alacritty_terminal/src/graphics/mod.rs
new file mode 100644
index 00000000..30424c2b
--- /dev/null
+++ b/alacritty_terminal/src/graphics/mod.rs
@@ -0,0 +1,146 @@
+//! This module implements the logic to manage graphic items included in a
+//! `Grid` instance.
+
+pub mod sixel;
+
+use std::mem;
+use std::sync::{Arc, Weak};
+
+use parking_lot::Mutex;
+use serde::{Deserialize, Serialize};
+
+use crate::term::color::Rgb;
+
+/// Max allowed dimensions (width, height) for the graphic, in pixels.
+pub const MAX_GRAPHIC_DIMENSIONS: (usize, usize) = (4096, 4096);
+
+/// Unique identifier for every graphic added to a grid.
+#[derive(Serialize, Deserialize, Eq, PartialEq, Clone, Debug, Copy, Hash, PartialOrd, Ord)]
+pub struct GraphicId(u64);
+
+/// Reference to a texture stored in the display.
+///
+/// When all references to a single texture are removed, its identifier is
+/// added to the remove queue.
+#[derive(Clone, Debug)]
+pub struct TextureRef {
+    /// Graphic identifier.
+    pub id: GraphicId,
+
+    /// Queue to track removed references.
+    pub remove_queue: Weak<Mutex<Vec<GraphicId>>>,
+}
+
+impl PartialEq for TextureRef {
+    fn eq(&self, t: &Self) -> bool {
+        // Ignore remove_queue.
+        self.id == t.id
+    }
+}
+
+impl Eq for TextureRef {}
+
+impl Drop for TextureRef {
+    fn drop(&mut self) {
+        if let Some(remove_queue) = self.remove_queue.upgrade() {
+            remove_queue.lock().push(self.id);
+        }
+    }
+}
+
+/// Graphic data stored in a single cell.
+#[derive(Eq, PartialEq, Clone, Debug)]
+pub struct GraphicCell {
+    /// Texture to draw the graphic in this cell.
+    pub texture: Arc<TextureRef>,
+
+    /// Offset in the x direction.
+    pub offset_x: u16,
+
+    /// Offset in the y direction.
+    pub offset_y: u16,
+}
+
+impl GraphicCell {
+    /// Graphic identifier of the texture in this cell.
+    #[inline]
+    pub fn graphic_id(&self) -> GraphicId {
+        self.texture.id
+    }
+}
+
+/// Specifies the format of the pixel data.
+#[derive(Serialize, Deserialize, Eq, PartialEq, Clone, Debug, Copy)]
+pub enum ColorType {
+    /// 3 bytes per pixel (red, green, blue).
+    Rgb,
+
+    /// 4 bytes per pixel (red, green, blue, alpha).
+    Rgba,
+}
+
+/// Defines a single graphic read from the PTY.
+#[derive(Serialize, Deserialize, Eq, PartialEq, Clone, Debug)]
+pub struct GraphicData {
+    /// Graphics identifier.
+    pub id: GraphicId,
+
+    /// Width, in pixels, of the graphic.
+    pub width: usize,
+
+    /// Height, in pixels, of the graphic.
+    pub height: usize,
+
+    /// Color type of the pixels.
+    pub color_type: ColorType,
+
+    /// Pixels data.
+    pub pixels: Vec<u8>,
+}
+
+/// Queues to add or to remove the textures in the display.
+pub struct UpdateQueues {
+    /// Graphics read from the PTY.
+    pub pending: Vec<GraphicData>,
+
+    /// Graphics removed from the grid.
+    pub remove_queue: Vec<GraphicId>,
+}
+
+/// Track changes in the grid to add or to remove graphics.
+#[derive(Clone, Debug, Default)]
+pub struct Graphics {
+    /// Last generated identifier.
+    pub last_id: u64,
+
+    /// New graphics, received from the PTY.
+    pub pending: Vec<GraphicData>,
+
+    /// Graphics removed from the grid.
+    pub remove_queue: Arc<Mutex<Vec<GraphicId>>>,
+
+    /// Shared palette for Sixel graphics.
+    pub sixel_shared_palette: Option<Vec<Rgb>>,
+}
+
+impl Graphics {
+    /// Generate a new graphic identifier.
+    pub fn next_id(&mut self) -> GraphicId {
+        self.last_id += 1;
+        GraphicId(self.last_id)
+    }
+
+    /// Get queues to update graphics in the grid.
+    ///
+    /// If all queues are empty, it returns `None`.
+    pub fn take_queues(&mut self) -> Option<UpdateQueues> {
+        let mut remove_queue = self.remove_queue.lock();
+        if remove_queue.is_empty() && self.pending.is_empty() {
+            return None;
+        }
+
+        let remove_queue = mem::take(&mut *remove_queue);
+
+        Some(UpdateQueues { pending: mem::take(&mut self.pending), remove_queue })
+    }
+}
diff --git a/alacritty_terminal/src/graphics/sixel.rs b/alacritty_terminal/src/graphics/sixel.rs
new file mode 100644
index 00000000..476089cc
--- /dev/null
+++ b/alacritty_terminal/src/graphics/sixel.rs
@@ -0,0 +1,772 @@
+//! This module implements a parser for the Sixel protocol, and it is based on the
+//! chapter [SIXEL GRAPHICS EXTENSION] of the DEC reference manual.
+//!
+//! [SIXEL GRAPHICS EXTENSION]: https://archive.org/details/bitsavers_decstandar0VideoSystemsReferenceManualDec91_74264381/page/n907/mode/2up
+//!
+//! # Limitations
+//!
+//! The parser have the following limitations:
+//!
+//! * A single image can use up to 1024 different colors.
+//!
+//!   The Sixel reference requires 256, but allow more colors.
+//!
+//! * Image dimensions are limited to 4096 x 4096.
+//!
+//! * Pixel aspect ratio parameters are ignored.
+//!
+//!   The Sixel references specifies some parameters to change the pixel
+//!   aspect ratio, but multiple implementations always use 1:1, so these
+//!   parameters have no real effect.
+use std::cmp::max;
+use std::fmt;
+use std::mem;
+
+use crate::graphics::{ColorType, GraphicData, GraphicId, MAX_GRAPHIC_DIMENSIONS};
+use crate::term::color::Rgb;
+
+use log::trace;
+use vte::Params;
+
+/// Type for color registers.
+#[derive(Copy, Clone, Default, Debug, PartialEq, Eq)]
+struct ColorRegister(u16);
+
+/// Number of color registers.
+const MAX_COLOR_REGISTERS: usize = 1024;
+
+/// Color register for transparent pixels.
+const REG_TRANSPARENT: ColorRegister = ColorRegister(u16::MAX);
+
+/// Number of parameters allowed in a single Sixel command.
+const MAX_COMMAND_PARAMS: usize = 5;
+
+#[derive(Debug)]
+pub enum Error {
+    /// Image dimensions are too big.
+    TooBigImage { width: usize, height: usize },
+
+    /// A component in a color introducer is not valid.
+    InvalidColorComponent { register: u16, component_value: u16 },
+
+    /// The coordinate system to define the color register is not valid.
+    InvalidColorCoordinateSystem { register: u16, coordinate_system: u16 },
+}
+
+impl fmt::Display for Error {
+    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Error::TooBigImage { width, height } => {
+                write!(fmt, "The image dimensions are too big ({}, {})", width, height)
+            },
+
+            Error::InvalidColorComponent { register, component_value } => {
+                write!(fmt, "Invalid color component {} for register {}", component_value, register)
+            },
+
+            Error::InvalidColorCoordinateSystem { register, coordinate_system } => {
+                write!(
+                    fmt,
+                    "Invalid color coordinate system {} for register {}",
+                    coordinate_system, register
+                )
+            },
+        }
+    }
+}
+
+/// Commands found in the data stream.
+#[derive(Debug)]
+enum SixelCommand {
+    /// Specifies a repeat count before a sixel.
+    ///
+    /// Its only parameter is the repeat count.
+    RepeatIntroducer,
+
+    /// Defines raster attributes for the following data.
+    ///
+    /// It expects 4 parameters:
+    ///
+    /// 1. Pixel aspect ratio numerator (relative height).
+    /// 2. Pixel aspect ratio denominator (relative width).
+    /// 3. Horizontal Extent.
+    /// 4. Vertical Extent.
+    SetRasterAttributes,
+
+    /// Starts a color selection sequence.
+    ///
+    /// The first parameter is the register number.
+    ///
+    /// Optionally, it can receive 4 more parameters:
+    ///
+    /// 1. Color coordinate system. `1` for HLS, `2` for RGB.
+    /// 2. Hue angle, or red.
+    /// 3. Lightness, or green.
+    /// 4. Saturation, or blue.
+    ColorIntroducer,
+
+    /// Moves the active position to the graphic left margin.
+    CarriageReturn,
+
+    /// Moves the active position to the graphic left margin
+    /// and one row of sixels.
+    NextLine,
+}
+
+/// Parser for commands found in the picture definition.
+#[derive(Debug)]
+struct CommandParser {
+    /// Active command.
+    command: SixelCommand,
+
+    /// Parameter values.
+    ///
+    /// If a value is greater than `u16::MAX`, it will be kept as `u16::MAX`.
+    ///
+    /// Parameters after `MAX_COMMAND_PARAMS` are ignored.
+    params: [u16; MAX_COMMAND_PARAMS],
+
+    /// Current position.
+    params_position: usize,
+}
+
+impl CommandParser {
+    fn new(command: SixelCommand) -> CommandParser {
+        CommandParser { command, params: [0; MAX_COMMAND_PARAMS], params_position: 0 }
+    }
+
+    fn put(&mut self, byte: u8) {
+        let pos = self.params_position;
+        if pos < MAX_COMMAND_PARAMS {
+            match byte {
+                b'0'..=b'9' => {
+                    self.params[pos] =
+                        self.params[pos].saturating_mul(10).saturating_add((byte - b'0') as u16);
+                },
+
+                b';' => {
+                    self.params_position += 1;
+                },
+
+                _ => (), // Ignore unknown bytes.
+            }
+        }
+    }
+
+    /// Apply the execution of the active command to the parser.
+    fn finish(self, parser: &mut Parser) -> Result<(), Error> {
+        match self.command {
+            SixelCommand::RepeatIntroducer => {
+                parser.repeat_count = self.params[0] as usize;
+            },
+
+            SixelCommand::SetRasterAttributes => {
+                if self.params_position >= 3 {
+                    let width = self.params[2] as usize;
+                    let height = self.params[3] as usize;
+                    parser.ensure_size(width, height)?;
+                }
+            },
+
+            SixelCommand::ColorIntroducer => {
+                let register = ColorRegister(self.params[0]);
+
+                if self.params_position >= 4 {
+                    macro_rules! p {
+                        ($index:expr) => {
+                            match self.params[$index] {
+                                x if x <= 100 => x,
+                                x => {
+                                    return Err(Error::InvalidColorComponent {
+                                        register: register.0,
+                                        component_value: x,
+                                    })
+                                },
+                            }
+                        };
+                    }
+
+                    let (r, g, b) = match self.params[1] {
+                        // HLS.
+                        1 => hls_to_rgb(p!(2), p!(3), p!(4)),
+
+                        // RGB.
+                        2 => (p!(2), p!(3), p!(4)),
+
+                        // Invalid coordinate system.
+                        x => {
+                            return Err(Error::InvalidColorCoordinateSystem {
+                                register: register.0,
+                                coordinate_system: x,
+                            })
+                        },
+                    };
+
+                    parser.set_color_register(register, r, g, b);
+                }
+
+                parser.selected_color_register = register;
+            },
+
+            SixelCommand::CarriageReturn => {
+                parser.x = 0;
+            },
+
+            SixelCommand::NextLine => {
+                parser.x = 0;
+                parser.y += 6;
+            },
+        }
+
+        Ok(())
+    }
+}
+
+/// A group of 6 vertical pixels.
+struct Sixel(u8);
+
+impl Sixel {
+    /// Create a new sixel.
+    ///
+    /// It expects the byte value from the picture definition stream.
+    #[inline]
+    fn new(byte: u8) -> Sixel {
+        debug_assert!((0x3F..=0x7E).contains(&byte));
+        Sixel(byte - 0x3F)
+    }
+
+    /// Return how many rows are printed in the sixel.
+    #[inline]
+    fn height(&self) -> usize {
+        8 - self.0.leading_zeros() as usize
+    }
+
+    /// Return an iterator to get dots in the sixel.
+    #[inline]
+    fn dots(&self) -> impl Iterator<Item = bool> {
+        let sixel = self.0;
+        (0..6).map(move |position| sixel & (1 << position) != 0)
+    }
+}
+
+/// Parser of the picture definition in a Sixel data stream.
+#[derive(Default, Debug)]
+pub struct Parser {
+    /// Active command to be parsed.
+    command_parser: Option<CommandParser>,
+
+    /// Current picture width.
+    width: usize,
+
+    /// Current picture height.
+    height: usize,
+
+    /// Current picture pixels.
+    pixels: Vec<ColorRegister>,
+
+    /// Indicates the register color for empty pixels.
+    background: ColorRegister,
+
+    /// RGB values for every register.
+    color_registers: Vec<Rgb>,
+
+    /// Selected color register.
+    selected_color_register: ColorRegister,
+
+    /// Repeat count for the next sixel.
+    repeat_count: usize,
+
+    /// Horizontal position of the active sixel.
+    x: usize,
+
+    /// Vertical position of the active sixel.
+    y: usize,
+}
+
+impl Parser {
+    /// Creates a new parser.
+    pub fn new(params: &Params, shared_palette: Option<Vec<Rgb>>) -> Parser {
+        trace!("Start Sixel parser");
+
+        let mut parser = Parser::default();
+
+        // According to the Sixel reference, the second parameter (Ps2) is
+        // the background selector. It controls how to show pixels without
+        // an explicit color, and it accepts the following values:
+        //
+        //   0   device default action
+        //   1   no action (don't change zero value pixels)
+        //   2   set zero value pixels to background color
+        //
+        // We replicate the xterm's behaviour:
+        //
+        //  - If it is set to `1`, the background is transparent.
+        //  - For any other value, the background is the color register 0.
+
+        let ps2 = params.iter().nth(1).and_then(|param| param.iter().next().copied()).unwrap_or(0);
+        parser.background = if ps2 == 1 { REG_TRANSPARENT } else { ColorRegister(0) };
+
+        if let Some(color_registers) = shared_palette {
+            parser.color_registers = color_registers;
+        } else {
+            init_color_registers(&mut parser);
+        }
+
+        parser
+    }
+
+    /// Parse a byte from the Sixel stream.
+    pub fn put(&mut self, byte: u8) -> Result<(), Error> {
+        match byte {
+            b'!' => self.start_command(SixelCommand::RepeatIntroducer)?,
+
+            b'"' => self.start_command(SixelCommand::SetRasterAttributes)?,
+
+            b'#' => self.start_command(SixelCommand::ColorIntroducer)?,
+
+            b'$' => self.start_command(SixelCommand::CarriageReturn)?,
+
+            b'-' => self.start_command(SixelCommand::NextLine)?,
+
+            b'0'..=b'9' | b';' => {
+                if let Some(command_parser) = &mut self.command_parser {
+                    command_parser.put(byte);
+                }
+            },
+
+            0x3F..=0x7E => self.add_sixel(Sixel::new(byte))?,
+
+            _ => {
+                // Invalid bytes are ignored, but we still have to finish any
+                // active command.
+
+                self.finish_command()?;
+            },
+        }
+
+        Ok(())
+    }
+
+    #[inline]
+    fn start_command(&mut self, command: SixelCommand) -> Result<(), Error> {
+        self.finish_command()?;
+        self.command_parser = Some(CommandParser::new(command));
+        Ok(())
+    }
+
+    #[inline]
+    fn finish_command(&mut self) -> Result<(), Error> {
+        if let Some(command_parser) = self.command_parser.take() {
+            command_parser.finish(self)?;
+        }
+
+        Ok(())
+    }
+
+    /// Set the RGB color for a register.
+    ///
+    /// Color components are expected to be in the range of 0..=100.
+    fn set_color_register(&mut self, register: ColorRegister, r: u16, g: u16, b: u16) {
+        let register = register.0 as usize;
+
+        if register >= MAX_COLOR_REGISTERS {
+            return;
+        }
+
+        if self.color_registers.len() <= register {
+            self.color_registers.resize(register + 1, Rgb { r: 0, g: 0, b: 0 })
+        }
+
+        let r = ((r * 255 + 50) / 100) as u8;
+        let g = ((g * 255 + 50) / 100) as u8;
+        let b = ((b * 255 + 50) / 100) as u8;
+        self.color_registers[register] = Rgb { r, g, b };
+    }
+
+    /// Check if the current picture is big enough for the given dimensions. If
+    /// not, the picture is resized.
+    fn ensure_size(&mut self, width: usize, height: usize) -> Result<(), Error> {
+        // Do nothing if the current picture is big enough.
+        if self.width >= width && self.height >= height {
+            return Ok(());
+        }
+
+        if width > MAX_GRAPHIC_DIMENSIONS.0 || height > MAX_GRAPHIC_DIMENSIONS.1 {
+            return Err(Error::TooBigImage { width, height });
+        }
+
+        trace!(
+            "Set Sixel image dimensions to {}x{}",
+            max(self.width, width),
+            max(self.height, height),
+        );
+
+        // If there is no current picture, creates a new one.
+        if self.pixels.is_empty() {
+            self.width = width;
+            self.height = height;
+            self.pixels = vec![self.background; width * height];
+            return Ok(());
+        }
+
+        // If current width is big enough, we only need to add more pixels
+        // after the current buffer.
+        if self.width >= width {
+            self.pixels.resize(height * self.width, self.background);
+            self.height = height;
+            return Ok(());
+        }
+
+        // At this point, we know that the new width is greater than the
+        // current one, so we have to extend the buffer and move the rows to
+        // their new positions.
+        let height = usize::max(height, self.height);
+
+        self.pixels.resize(height * width, self.background);
+
+        for y in (0..self.height).rev() {
+            for x in (0..self.width).rev() {
+                let old = y * self.width + x;
+                let new = y * width + x;
+                self.pixels.swap(old, new);
+            }
+        }
+
+        self.width = width;
+        self.height = height;
+        Ok(())
+    }
+
+    /// Add a sixel using the selected color register, and move the active
+    /// position.
+    fn add_sixel(&mut self, sixel: Sixel) -> Result<(), Error> {
+        self.finish_command()?;
+
+        // Take the repeat count and reset it.
+        //
+        // `max` function is used because the Sixel reference specifies
+        // that a repeat count of zero implies a repeat count of 1.
+        let repeat = max(1, mem::take(&mut self.repeat_count));
+
+        self.ensure_size(self.x + repeat, self.y + sixel.height())?;
+
+        if sixel.0 != 0 {
+            let mut index = self.width * self.y + self.x;
+            for dot in sixel.dots() {
+                if dot {
+                    for pixel in &mut self.pixels[index..index + repeat] {
+                        *pixel = self.selected_color_register;
+                    }
+                }
+
+                index += self.width;
+            }
+        }
+
+        self.x += repeat;
+
+        Ok(())
+    }
+
+    /// Returns the final graphic to append to the grid, with the palette
+    /// built in the process.
+    pub fn finish(mut self) -> Result<(GraphicData, Vec<Rgb>), Error> {
+        self.finish_command()?;
+
+        trace!(
+            "Finish Sixel parser: width={}, height={}, color_registers={}",
+            self.width,
+            self.height,
+            self.color_registers.len()
+        );
+
+        let mut rgba_pixels = Vec::with_capacity(self.pixels.len() * 4);
+
+        for &register in &self.pixels {
+            let pixel = {
+                if register == REG_TRANSPARENT {
+                    [0; 4]
+                } else {
+                    match self.color_registers.get(register.0 as usize) {
+                        None => [0, 0, 0, 255],
+                        Some(color) => [color.r, color.g, color.b, 255],
+                    }
+                }
+            };
+
+            rgba_pixels.extend_from_slice(&pixel);
+        }
+
+        let data = GraphicData {
+            id: GraphicId(0),
+            height: self.height,
+            width: self.width,
+            color_type: ColorType::Rgba,
+            pixels: rgba_pixels,
+        };
+
+        Ok((data, self.color_registers))
+    }
+}
+
+/// Compute a RGB value from HLS.
+///
+/// Input and output values are in the range of `0..=100`.
+///
+/// The implementation is a direct port of the same function in the
+/// xterm's code.
+#[allow(clippy::many_single_char_names)]
+fn hls_to_rgb(h: u16, l: u16, s: u16) -> (u16, u16, u16) {
+    if s == 0 {
+        return (l, l, l);
+    }
+
+    let hs = ((h + 240) / 60) % 6;
+    let lv = l as f64 / 100.0;
+
+    let c2 = f64::abs((2.0 * lv as f64) - 1.0);
+    let c = (1.0 - c2) * (s as f64 / 100.0);
+    let x = if hs & 1 == 1 { c } else { 0.0 };
+
+    let rgb = match hs {
+        0 => (c, x, 0.),
+        1 => (x, c, 0.),
+        2 => (0., c, x),
+        3 => (0., x, c),
+        4 => (x, 0., c),
+        _ => (c, 0., c),
+    };
+
+    fn clamp(x: f64) -> u16 {
+        let x = x * 100. + 0.5;
+        if x > 100. {
+            100
+        } else if x < 0. {
+            0
+        } else {
+            x as u16
+        }
+    }
+
+    let m = lv - 0.5 * c;
+    let r = clamp(rgb.0 + m);
+    let g = clamp(rgb.1 + m);
+    let b = clamp(rgb.2 + m);
+
+    (r, g, b)
+}
+
+/// Initialize the color registers using the colors from the VT-340 terminal.
+///
+/// There is no official documentation about these colors, but multiple Sixel
+/// implementations assume this palette.
+fn init_color_registers(parser: &mut Parser) {
+    parser.set_color_register(ColorRegister(0), 0, 0, 0);
+    parser.set_color_register(ColorRegister(1), 20, 20, 80);
+    parser.set_color_register(ColorRegister(2), 80, 13, 13);
+    parser.set_color_register(ColorRegister(3), 20, 80, 20);
+    parser.set_color_register(ColorRegister(4), 80, 20, 80);
+    parser.set_color_register(ColorRegister(5), 20, 80, 80);
+    parser.set_color_register(ColorRegister(6), 80, 80, 20);
+    parser.set_color_register(ColorRegister(7), 53, 53, 53);
+    parser.set_color_register(ColorRegister(8), 26, 26, 26);
+    parser.set_color_register(ColorRegister(9), 33, 33, 60);
+    parser.set_color_register(ColorRegister(10), 60, 26, 26);
+    parser.set_color_register(ColorRegister(11), 33, 60, 33);
+    parser.set_color_register(ColorRegister(12), 60, 33, 60);
+    parser.set_color_register(ColorRegister(13), 33, 60, 60);
+    parser.set_color_register(ColorRegister(14), 60, 60, 33);
+    parser.set_color_register(ColorRegister(15), 80, 80, 80);
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use std::fs;
+    use std::path::Path;
+
+    macro_rules! put_bytes {
+        ($parser:expr, $data:expr) => {
+            #[allow(clippy::string_lit_as_bytes)]
+            for &byte in $data.as_bytes() {
+                let _ = $parser.put(byte);
+            }
+        };
+    }
+
+    #[test]
+    fn parse_command_parameters() {
+        let mut command_parser = CommandParser::new(SixelCommand::ColorIntroducer);
+        put_bytes!(command_parser, "65535;1;2;3;4;5");
+
+        assert_eq!(command_parser.params_position, 5);
+        assert_eq!(command_parser.params[0], 65535);
+        assert_eq!(command_parser.params[1], 1);
+        assert_eq!(command_parser.params[2], 2);
+        assert_eq!(command_parser.params[3], 3);
+        assert_eq!(command_parser.params[4], 4);
+    }
+
+    #[test]
+    fn set_color_registers() {
+        let mut parser = Parser::default();
+        put_bytes!(parser, "#1;2;30;100;0#200;1;20;75;50.");
+
+        assert!(parser.color_registers.len() >= 200);
+
+        assert_eq!(parser.color_registers[1], Rgb { r: 77, g: 255, b: 0 });
+        assert_eq!(parser.color_registers[200], Rgb { r: 161, g: 161, b: 224 });
+
+        assert_eq!(parser.selected_color_register.0, 200);
+    }
+
+    #[test]
+    fn convert_hls_colors() {
+        // This test converts values from HLS to RBG, and compares those
+        // results with the values generated by the xterm implementation
+        // of the same function.
+
+        assert_eq!(hls_to_rgb(100, 60, 60), (84, 36, 84));
+        assert_eq!(hls_to_rgb(60, 100, 60), (100, 100, 100));
+        assert_eq!(hls_to_rgb(30, 30, 60), (12, 12, 48));
+        assert_eq!(hls_to_rgb(100, 90, 100), (100, 80, 100));
+        assert_eq!(hls_to_rgb(100, 0, 90), (0, 0, 0));
+        assert_eq!(hls_to_rgb(0, 90, 30), (87, 87, 93));
+        assert_eq!(hls_to_rgb(60, 0, 60), (0, 0, 0));
+        assert_eq!(hls_to_rgb(30, 0, 0), (0, 0, 0));
+        assert_eq!(hls_to_rgb(30, 90, 30), (87, 87, 93));
+        assert_eq!(hls_to_rgb(30, 30, 30), (21, 21, 39));
+        assert_eq!(hls_to_rgb(90, 100, 60), (100, 100, 100));
+        assert_eq!(hls_to_rgb(0, 0, 0), (0, 0, 0));
+        assert_eq!(hls_to_rgb(30, 0, 90), (0, 0, 0));
+        assert_eq!(hls_to_rgb(100, 60, 90), (96, 24, 96));
+        assert_eq!(hls_to_rgb(30, 30, 0), (30, 30, 30));
+    }
+
+    #[test]
+    fn resize_picture() -> Result<(), Error> {
+        let mut parser = Parser { background: REG_TRANSPARENT, ..Parser::default() };
+
+        const WIDTH: usize = 30;
+        const HEIGHT: usize = 20;
+
+        // Initialize a transparent picture with Set Raster Attributes.
+        put_bytes!(parser, format!("\"1;1;{};{}.", WIDTH, HEIGHT));
+
+        assert_eq!(parser.width, WIDTH);
+        assert_eq!(parser.height, HEIGHT);
+        assert_eq!(parser.pixels.len(), WIDTH * HEIGHT);
+
+        assert!(parser.pixels.iter().all(|&pixel| pixel == REG_TRANSPARENT));
+
+        // Fill each row with a different color register.
+        for (n, row) in parser.pixels.chunks_mut(WIDTH).enumerate() {
+            row.iter_mut().for_each(|pixel| *pixel = ColorRegister(n as u16));
+        }
+
+        // Increase height.
+        //
+        // New rows must be transparent.
+        parser.ensure_size(WIDTH, HEIGHT + 5)?;
+
+        assert_eq!(parser.width, WIDTH);
+        assert_eq!(parser.height, HEIGHT + 5);
+        assert_eq!(parser.pixels.len(), WIDTH * (HEIGHT + 5));
+
+        for (n, row) in parser.pixels.chunks(WIDTH).enumerate() {
+            let expected = if n < HEIGHT { ColorRegister(n as u16) } else { REG_TRANSPARENT };
+            assert!(row.iter().all(|pixel| *pixel == expected));
+        }
+
+        // Increase both width and height.
+        //
+        // New rows and columns must be transparent.
+        parser.ensure_size(WIDTH + 5, HEIGHT + 10)?;
+
+        assert_eq!(parser.width, WIDTH + 5);
+        assert_eq!(parser.height, HEIGHT + 10);
+        assert_eq!(parser.pixels.len(), (WIDTH + 5) * (HEIGHT + 10));
+
+        for (n, row) in parser.pixels.chunks(WIDTH + 5).enumerate() {
+            if n < HEIGHT {
+                assert!(row[..WIDTH].iter().all(|pixel| *pixel == ColorRegister(n as u16)));
+                assert!(row[WIDTH..].iter().all(|pixel| *pixel == REG_TRANSPARENT));
+            } else {
+                assert!(row.iter().all(|pixel| *pixel == REG_TRANSPARENT));
+            }
+        }
+
+        Ok(())
+    }
+
+    #[test]
+    fn sixel_height() {
+        assert_eq!(Sixel(0b000000).height(), 0);
+        assert_eq!(Sixel(0b000001).height(), 1);
+        assert_eq!(Sixel(0b000100).height(), 3);
+        assert_eq!(Sixel(0b000101).height(), 3);
+        assert_eq!(Sixel(0b101111).height(), 6);
+    }
+
+    #[test]
+    fn sixel_positions() {
+        macro_rules! dots {
+            ($sixel:expr) => {
+                Sixel($sixel).dots().collect::<Vec<_>>()
+            };
+        }
+
+        assert_eq!(dots!(0b000000), &[false, false, false, false, false, false,]);
+        assert_eq!(dots!(0b000001), &[true, false, false, false, false, false,]);
+        assert_eq!(dots!(0b000100), &[false, false, true, false, false, false,]);
+        assert_eq!(dots!(0b000101), &[true, false, true, false, false, false,]);
+        assert_eq!(dots!(0b101111), &[true, true, true, true, false, true,]);
+    }
+
+    #[test]
+    fn load_sixel_files() {
+        let images_dir = Path::new(concat!(env!("CARGO_MANIFEST_DIR"), "/tests/sixel"));
+
+        let test_images = ["testimage_im6", "testimage_libsixel", "testimage_ppmtosixel"];
+
+        for test_image in &test_images {
+            // Load Sixel data.
+            let mut sixel = {
+                let mut path = images_dir.join(test_image);
+                path.set_extension("sixel");
+                fs::read(path).unwrap()
+            };
+
+            // Remove DCS sequence from Sixel data.
+            let dcs_end = sixel.iter().position(|&byte| byte == b'q').unwrap();
+            sixel.drain(..=dcs_end);
+
+            // Remove ST, which can be either "1B 5C" or "9C". To simplify the
+            // code, we assume that any ESC byte is the start of the ST.
+            if let Some(pos) = sixel.iter().position(|&b| b == 0x1B || b == 0x9C) {
+                sixel.truncate(pos);
+            }
+
+            // Parse the data and get the GraphicData item.
+            let mut parser = Parser::default();
+            for byte in sixel {
+                parser.put(byte).unwrap();
+            }
+
+            let graphics = parser.finish().unwrap().0;
+
+            assert_eq!(graphics.width, 64);
+            assert_eq!(graphics.height, 64);
+
+            // Read the RGBA stream generated by ImageMagick and compare it
+            // with our picture.
+            let expected_rgba = {
+                let mut path = images_dir.join(test_image);
+                path.set_extension("rgba");
+                fs::read(path).unwrap()
+            };
+
+            assert_eq!(graphics.pixels, expected_rgba);
+        }
+    }
+}
diff --git a/alacritty_terminal/src/lib.rs b/alacritty_terminal/src/lib.rs
index c1ba3690..ea4a2a24 100644
--- a/alacritty_terminal/src/lib.rs
+++ b/alacritty_terminal/src/lib.rs
@@ -8,6 +8,7 @@ pub mod ansi;
 pub mod config;
 pub mod event;
 pub mod event_loop;
+pub mod graphics;
 pub mod grid;
 pub mod index;
 pub mod selection;
diff --git a/alacritty_terminal/src/term/cell.rs b/alacritty_terminal/src/term/cell.rs
index 64de5492..18aad87d 100644
--- a/alacritty_terminal/src/term/cell.rs
+++ b/alacritty_terminal/src/term/cell.rs
@@ -4,6 +4,7 @@ use bitflags::bitflags;
 use serde::{Deserialize, Serialize};
 
 use crate::ansi::{Color, NamedColor};
+use crate::graphics::GraphicCell;
 use crate::grid::{self, GridCell};
 use crate::index::Column;
 
@@ -24,6 +25,7 @@ bitflags! {
         const STRIKEOUT                 = 0b0000_0010_0000_0000;
         const LEADING_WIDE_CHAR_SPACER  = 0b0000_0100_0000_0000;
         const DOUBLE_UNDERLINE          = 0b0000_1000_0000_0000;
+        const GRAPHICS                  = 0b0001_0000_0000_0000;
     }
 }
 
@@ -53,6 +55,9 @@ impl ResetDiscriminant<Color> for Cell {
 #[derive(Serialize, Deserialize, Default, Debug, Clone, Eq, PartialEq)]
 struct CellExtra {
     zerowidth: Vec<char>,
+
+    #[serde(skip)]
+    graphic: Option<Box<GraphicCell>>,
 }
 
 /// Content and attributes of a single cell in the terminal grid.
@@ -107,6 +112,21 @@ impl Cell {
         self.drop_extra();
         self.c = ' ';
     }
+
+    /// Graphic present in the cell.
+    #[inline]
+    pub fn graphic(&self) -> Option<&GraphicCell> {
+        self.extra.as_deref().and_then(|extra| extra.graphic.as_deref())
+    }
+
+    /// Write the graphic data in the cell.
+    #[inline]
+    pub fn set_graphic(&mut self, graphic_cell: GraphicCell) {
+        let mut extra = self.extra.get_or_insert_with(Default::default);
+        extra.graphic = Some(Box::new(graphic_cell));
+
+        self.flags_mut().insert(Flags::GRAPHICS);
+    }
 }
 
 impl GridCell for Cell {
@@ -122,7 +142,8 @@ impl GridCell for Cell {
                     | Flags::STRIKEOUT
                     | Flags::WRAPLINE
                     | Flags::WIDE_CHAR_SPACER
-                    | Flags::LEADING_WIDE_CHAR_SPACER,
+                    | Flags::LEADING_WIDE_CHAR_SPACER
+                    | Flags::GRAPHICS,
             )
             && self.extra.as_ref().map(|extra| extra.zerowidth.is_empty()) != Some(false)
     }
diff --git a/alacritty_terminal/src/term/mod.rs b/alacritty_terminal/src/term/mod.rs
index 1808f3aa..1e87ec8a 100644
--- a/alacritty_terminal/src/term/mod.rs
+++ b/alacritty_terminal/src/term/mod.rs
@@ -1,6 +1,7 @@
 //! Exports the `Term` type which is a high-level API for the Grid.
 
 use std::cmp::{max, min};
+use std::fmt::Write;
 use std::ops::{Index, IndexMut, Range};
 use std::sync::Arc;
 use std::{mem, ptr, str};
@@ -9,12 +10,16 @@ use bitflags::bitflags;
 use log::{debug, trace};
 use serde::{Deserialize, Serialize};
 use unicode_width::UnicodeWidthChar;
+use vte::Params;
 
 use crate::ansi::{
     self, Attr, CharsetIndex, Color, CursorShape, CursorStyle, Handler, NamedColor, StandardCharset,
 };
 use crate::config::Config;
 use crate::event::{Event, EventListener};
+use crate::graphics::{
+    sixel, GraphicCell, GraphicData, Graphics, TextureRef, UpdateQueues, MAX_GRAPHIC_DIMENSIONS,
+};
 use crate::grid::{Dimensions, Grid, GridIterator, Scroll};
 use crate::index::{self, Boundary, Column, Direction, Line, Point, Side};
 use crate::selection::{Selection, SelectionRange};
@@ -62,6 +67,8 @@ bitflags! {
         const ALTERNATE_SCROLL    = 0b0000_1000_0000_0000_0000;
         const VI                  = 0b0001_0000_0000_0000_0000;
         const URGENCY_HINTS       = 0b0010_0000_0000_0000_0000;
+        const SIXEL_SCROLLING     = 0b0100_0000_0000_0000_0000;
+        const SIXEL_PRIV_PALETTE  = 0b1000_0000_0000_0000_0000;
         const ANY                 = std::u32::MAX;
     }
 }
@@ -72,6 +79,8 @@ impl Default for TermMode {
             | TermMode::LINE_WRAP
             | TermMode::ALTERNATE_SCROLL
             | TermMode::URGENCY_HINTS
+            | TermMode::SIXEL_SCROLLING
+            | TermMode::SIXEL_PRIV_PALETTE
     }
 }
 
@@ -269,6 +278,9 @@ pub struct Term<T> {
     /// Information about cell dimensions.
     cell_width: usize,
     cell_height: usize,
+
+    /// Data to add graphics to a grid.
+    graphics: Graphics,
 }
 
 impl<T> Term<T> {
@@ -320,6 +332,7 @@ impl<T> Term<T> {
             selection: None,
             cell_width: size.cell_width as usize,
             cell_height: size.cell_height as usize,
+            graphics: Graphics::default(),
         }
     }
 
@@ -470,6 +483,12 @@ impl<T> Term<T> {
         &mut self.grid
     }
 
+    /// Get queues to update graphic data. If both queues are empty, it returns
+    /// `None`.
+    pub fn graphics_take_queues(&mut self) -> Option<UpdateQueues> {
+        self.graphics.take_queues()
+    }
+
     /// Resize terminal to new dimensions.
     pub fn resize(&mut self, size: SizeInfo) {
         self.cell_width = size.cell_width as usize;
@@ -1578,6 +1597,10 @@ impl<T: EventListener> Handler for Term<T> {
                 style.blinking = true;
                 self.event_proxy.send_event(Event::CursorBlinkingChange(true));
             },
+            ansi::Mode::SixelScrolling => self.mode.insert(TermMode::SIXEL_SCROLLING),
+            ansi::Mode::SixelPrivateColorRegisters => {
+                self.mode.insert(TermMode::SIXEL_PRIV_PALETTE)
+            },
         }
     }
 
@@ -1620,6 +1643,11 @@ impl<T: EventListener> Handler for Term<T> {
                 style.blinking = false;
                 self.event_proxy.send_event(Event::CursorBlinkingChange(false));
             },
+            ansi::Mode::SixelScrolling => self.mode.remove(TermMode::SIXEL_SCROLLING),
+            ansi::Mode::SixelPrivateColorRegisters => {
+                self.graphics.sixel_shared_palette = None;
+                self.mode.remove(TermMode::SIXEL_PRIV_PALETTE);
+            },
         }
     }
 
@@ -1742,6 +1770,88 @@ impl<T: EventListener> Handler for Term<T> {
         let text = format!("\x1b[8;{};{}t", self.screen_lines(), self.columns());
         self.event_proxy.send_event(Event::PtyWrite(text));
     }
+
+    fn start_sixel_graphic(&mut self, params: &Params) -> Option<Box<sixel::Parser>> {
+        let palette = self.graphics.sixel_shared_palette.take();
+        Some(Box::new(sixel::Parser::new(params, palette)))
+    }
+
+    fn insert_graphic(&mut self, graphic: GraphicData, palette: Option<Vec<Rgb>>) {
+        // Store last palette if we receive a new one, and it is shared.
+        if let Some(palette) = palette {
+            if !self.mode.contains(TermMode::SIXEL_PRIV_PALETTE) {
+                self.graphics.sixel_shared_palette = Some(palette);
+            }
+        }
+
+        if graphic.width > MAX_GRAPHIC_DIMENSIONS.0 || graphic.height > MAX_GRAPHIC_DIMENSIONS.1 {
+            return;
+        }
+
+        let width = graphic.width as u16;
+        let height = graphic.height as u16;
+
+        if width == 0 || height == 0 {
+            return;
+        }
+
+        // Add the graphic data to the pending queue.
+        let graphic_id = self.graphics.next_id();
+        self.graphics.pending.push(GraphicData { id: graphic_id, ..graphic });
+
+        // If SIXEL_SCROLLING is enabled, the start of the graphic is the
+        // cursor position, and the grid can be scrolled if the graphic is
+        // larger than the screen. The cursor is moved to the next line
+        // after the graphic.
+        //
+        // If it is disabled, the graphic starts at (0, 0), the grid is never
+        // scrolled, and the cursor position is unmodified.
+
+        let scrolling = self.mode.contains(TermMode::SIXEL_SCROLLING);
+
+        // Fill the cells under the graphic.
+        //
+        // The cell in the first column contains a reference to the graphic,
+        // with the offset from the start. Rest of the cells are empty.
+
+        let left = if scrolling { self.grid.cursor.point.column.0 } else { 0 };
+
+        let texture = Arc::new(TextureRef {
+            id: graphic_id,
+            remove_queue: Arc::downgrade(&self.graphics.remove_queue),
+        });
+
+        for (top, offset_y) in (0..).zip((0..height).step_by(self.cell_height)) {
+            let line = if scrolling {
+                self.grid.cursor.point.line
+            } else {
+                // Check if the image is beyond the screen limit.
+                if top >= self.screen_lines().0 {
+                    break;
+                }
+
+                Line(top)
+            };
+
+            // Store a reference to the graphic in the first column.
+            let graphic_cell = GraphicCell { texture: texture.clone(), offset_x: 0, offset_y };
+            let mut cell = Cell::default();
+            cell.set_graphic(graphic_cell);
+            self.grid[line][Column(left)] = cell;
+
+            for col in left + 1..self.cols().0 {
+                self.grid[line][Column(col)] = Cell::default();
+            }
+
+            if scrolling {
+                self.linefeed();
+            }
+        }
+
+        if scrolling {
+            self.carriage_return();
+        }
+    }
 }
 
 /// Terminal version for escape sequence reports.
diff --git a/alacritty_terminal/tests/sixel/README.md b/alacritty_terminal/tests/sixel/README.md
new file mode 100644
index 00000000..c01deae9
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/README.md
@@ -0,0 +1,50 @@
+# Images for Sixel tests
+
+The files in this directory are used to test the Sixel parser against images
+generated by real-world software:
+
+* `testimage_im6.sixel`
+
+    Generated with ImageMagick 6.9.10.
+
+    ```bash
+    convert "$SOURCE" testimage_im6.sixel
+    ```
+
+* `testimage_libsixel.sixel`
+
+    Generated with libsixel 1.8.6.
+
+    ```bash
+    img2sixel -o testimage_libsixel.sixel "$SOURCE"
+    ```
+
+* `testimage_ppmtosixel.sixel`
+
+    Generated with Netpbm 10.
+
+    ```bash
+    pngtopnm "$SOURCE" \
+        | ppmquant 256 \
+        | ppmtosixel   \
+        > testimage_ppmtosixel.sixel
+    ```
+
+In the previous commands, `$SOURCE` is defined as:
+
+    SOURCE="$(git rev-parse --show-toplevel)/alacritty/alacritty.png"
+
+The image is the [Alacritty icon](../../../extra/logo/compat/alacritty-term.png).
+
+To verify the results of the parser we include the raw RGBA data for each
+image. It was generated with this script:
+
+```bash
+for IMG in *.sixel
+do
+    convert "$IMG" png:- | convert -depth 8 png:- rgba:"${IMG/.sixel/.rgba}"
+done
+```
+
+We have to convert the Sixel to PNG before RGBA because, for some reason,
+ImageMagick can't transform from Sixel to RGBA directly.
diff --git a/alacritty_terminal/tests/sixel/testimage_im6.rgba b/alacritty_terminal/tests/sixel/testimage_im6.rgba
new file mode 100644
index 00000000..af6abfa3
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/testimage_im6.rgba
diff --git a/alacritty_terminal/tests/sixel/testimage_im6.sixel b/alacritty_terminal/tests/sixel/testimage_im6.sixel
new file mode 100644
index 00000000..80752a75
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/testimage_im6.sixel
@@ -0,0 +1 @@
+P0;0;0q"1;1;64;64#0;2;3;5;6#1;2;3;6;7#2;2;4;6;8#3;2;8;8;8#4;2;11;11;11#5;2;6;11;13#6;2;8;14;17#7;2;10;15;16#8;2;11;16;16#9;2;9;15;19#10;2;8;16;21#11;2;8;17;22#12;2;14;14;14#13;2;16;15;15#14;2;18;16;15#15;2;17;17;17#16;2;20;18;15#17;2;19;14;15#18;2;20;19;15#19;2;22;21;14#20;2;20;20;20#21;2;23;23;23#22;2;36;14;12#23;2;33;18;12#24;2;35;22;12#25;2;48;17;9#26;2;39;22;11#27;2;50;20;9#28;2;26;18;13#29;2;32;17;13#30;2;26;24;13#31;2;29;22;13#32;2;35;26;12#33;2;40;28;11#34;2;41;32;11#35;2;46;36;10#36;2;44;31;10#37;2;7;24;35#38;2;18;30;37#39;2;6;29;43#40;2;7;27;39#41;2;6;30;45#42;2;19;31;38#43;2;27;27;27#44;2;30;30;30#45;2;33;33;33#46;2;36;36;36#47;2;39;39;39#48;2;42;42;42#49;2;45;45;45#50;2;49;49;49#51;2;51;23;9#52;2;65;16;6#53;2;66;20;6#54;2;82;20;3#55;2;88;17;1#56;2;93;18;1#57;2;88;15;1#58;2;89;20;1#59;2;93;20;1#60;2;89;24;1#61;2;93;23;1#62;2;53;27;9#63;2;53;27;9#64;2;55;32;8#65;2;57;36;8#66;2;68;25;5#67;2;70;31;5#68;2;72;36;5#69;2;63;25;7#70;2;66;32;6#71;2;58;39;7#72;2;68;39;6#73;2;73;41;5#74;2;71;47;5#75;2;76;30;4#76;2;84;26;3#77;2;86;34;2#78;2;89;27;1#79;2;94;26;1#80;2;90;29;0#81;2;92;30;1#82;2;94;28;1#83;2;94;30;1#84;2;90;33;0#85;2;90;36;0#86;2;93;31;1#87;2;95;33;0#88;2;95;36;0#89;2;78;38;4#90;2;87;39;2#91;2;77;47;4#92;2;82;47;3#93;2;92;40;1#94;2;91;42;0#95;2;91;38;0#96;2;95;39;0#97;2;96;42;0#98;2;89;45;2#99;2;91;45;0#100;2;92;49;0#101;2;96;45;0#102;2;96;48;0#103;2;81;49;41#104;2;81;47;40#105;2;78;53;4#106;2;85;56;3#107;2;92;52;0#108;2;92;55;0#109;2;91;53;2#110;2;96;52;0#111;2;97;54;0#112;2;97;55;0#113;2;92;58;0#114;2;93;61;0#115;2;97;58;0#116;2;98;61;0#117;2;97;59;0#118;2;93;64;0#119;2;98;64;0#120;2;98;67;0#121;2;94;66;0#122;2;81;51;41#123;2;82;52;41#124;2;82;55;41#125;2;82;58;41#126;2;83;61;41#127;2;83;64;41#128;2;83;67;41#129;2;84;70;41#130;2;84;71;40#131;2;5;35;53#132;2;5;40;62#133;2;5;42;64#134;2;4;46;71#135;2;8;45;69#136;2;4;48;75#137;2;35;51;61#138;2;35;53;64#139;2;4;51;80#140;2;5;56;88#141;2;3;60;97#142;2;2;62;100#143;2;4;62;100#144;2;4;59;95#145;2;6;63;100#146;2;10;65;100#147;2;13;66;100#148;2;22;70;100#149;2;35;75;100#150;2;43;78;100#151;2;49;80;100#152;2;52;52;52#153;2;54;54;54#154;2;58;58;58#155;2;61;61;61#156;2;65;65;65#157;2;66;66;66#158;2;71;71;71#159;2;54;71;82#160;2;73;85;93#161;2;65;85;98#162;2;67;84;94#163;2;75;90;100#164;2;78;78;78#165;2;76;91;100#166;2;87;95;100#167;2;91;96;100#168;2;94;98;100#169;2;91;96;100#170;2;100;100;100#171;2;96;98;100#172;2;0;0;0#172~~~N!56FN~~~$#57???OO#55OO#58!4O#60OOO#78OOO#80!4O#84O#81O#88!4G#96GGG#97GG#94!4O#99!5O#107O?OO?O#128?!7_#129___#130___$#104???_#103!5_??_#123!7_!4?_#125_?!5_?_#102???GGG#127_?!7_#116??GGG#114!4O#118OOO#121O$#56!4?GG#59GGG#61GGG#79GG?G#83GGG#124!4_??_#95???OO#126_?!6_?_#100?O#111?G#108O?!4O#113OO#119!4G#120GGG$#122!9?__#82???G#87!4?!4G#86O#85!5O#93??O#101!4G#110???!5G#112?G#115!4G-#156G][MCEECCEECECEECEECEC!4ECECEECECEECECEEECACCEECECECCEECECM[]KW$#157C?A@B@@BB@@B@B@@B@@B@B!4@B@B@@B@B@@B@B@@@B@BB@@B@B@BB@@B@B@B?AC$#155o__oG#4O?_??_#152!4?G!5?G!5?GG#2!4?O!9?O!6?O!6?O#0_#12_#155__o_$#164A@#158@#12?_#0_#153!9G?!5G?!5G??!19G?!10G#47O#158?@#164@A$#172@#47???O#154G#5_?__?!4_?!9_?!9_?__?!14_?!4_#4O#172!4?@$#2!6?O??O?O?O??O#0!6?O#1!11?O!9?O#152??G$#3!7?OO?O?O?Oo?!6O?Oo!7O?O?OOo!4O?O?!4O?OOoOOO$#4!35?_#155!7?C-#154wgoo#4@#2~#6!15~n~~{~^B!8?B^!5~n!14~#1B#4A#154wgow$#155EVNN#7A#9!16?O??A#29?_??@@!6?_#9!5?O#2!14?{#7O#155FVNE$#156@#12???{#5!19?@#13??C!7?@C#12!22?l#156???@$#25!27?G!8?G$#54!27?O!8?O$#61!27?!7_o__$#52!28?A!6?A$#56!28?CEEEMEEC$#59!28?!4WOWGW$#17!28?@#22??!4@-#153{wY{#12B#1K#6!6~v!11~F@#79EECAAA!4?CE#6@N!18~#2~#12T#153]ww{$#154BFDB#13{#2r#9!6?G#7!11?G#13A!5?__!5?A#23O#13!19?i#154@FFB$#152??_#29!21?O#76G!5?GG!5?G#66_#152!20?_$#66!24?_#83Oooo_O??Oo_ooO$#27!25?C#82GGG[GCCMG]GG#27C$#87!25?_#53@#61@B@D@B@F@B#53@#87_$#81!30?_??_$#51!31?OO-#50goo_#13E#0O#6!12~n~~^F!6?_{^^{_!6?F^!8~v!6~#1B#14s#50o_oo$#152VMH^#14g#2N#9!12?O#14??_?@#87AFBABB!4?BBABBE#17@#24G#15_#9!8?G#2!6?{#15J#152N^EN$#153?@A#15?@#3_#96!16?___o__!8?__o___#137!20?G$??C#16?O#24!17?G#88W[G[[K!6?K[[KWW#67O#153!20?@$#67!22?O#51A#86@#83??@!8?@#86??@#51A$#77!23?C#62!4?_!6?_$#85!28?O#7O!4?O#77O!4?C$#26!29?G!4?G$#75!29?C!4?C$#28!30?A#10_#9_#19A$#69!30?@#53??@-#49{wuw#14B#2~#6~~z!8~^~N@!6?w}NB??BN}g!6?@N!13~#0A#15[#49ysws$#50BFHF#15S#9???C#7!8?_??A#97CFEEME#31C!8?C#7_!5?A#18O#1!13?@#16@#50DJFJ$#20!4?g#16!14?O#101o!4WO#8_#70A!8?A#97!5EC#24C#64_#2!13?{#20_$#64!19?_#24C#102!4_#98_#33O#13?@#138_!4?_#14@#5O#96!5@#63@#68G#28!15?A$#68!20?G#63@#93?@???@!8?@#33O#101WWWwWO$#90!21?A#96??@@@#10??O#159G??G#11O#89??G#98_#102__?__$#89!26?G#170???_{{_#90!8?A$#38!30?C#137@@#42C$#167!30?O#160AA#169O-#47o__O#15@#2~#6!10~^F!6?o{~~@!6?@~~wo!6?F^!7~z~~#2~#15H#48}]K^$M[^m#20}#8!11?_#14G#110GIMKKC#31G#18A#37??A!6?A#9??C#102BBB@B#98@#7@#19G#8_#9!7?C#20???u#49@@B$@B?@#65!13?O#111o!4OG#72C#64@#40??_!6?_#16??A#31G#110CKMKMG#65O#47!14?_o_$#109!17?_#7@#102C@!4B#133???O!6?O#64??@#72C#111G!4Oo#109_$#33!18?A#112!4_#36_#135!4?C!6?C#36!4?_#112!4_#26A$#73!18?C#98@#92???O#140!4?G!6?G#92!4?O#73!4?C$#145!29?_!4?_$#146!29?O!4?O$#148!29?G!4?G$#151!29?C!4?C$#162!29?@!4?@$#165!29?A!4?A$#149!30?_??_$#161!30?O??O$#166!30?G??G$#168!30?C??C$#170!30?BNNB$#167!31?__$#171!31?OO-#46!4w#20b#1G#6!7~|NB!5?_w}!4~}o!4?o}!4~}w!6?BN|!7~#2~#20N#46wwws$#47!4F#21[#2v#9!7?A#8O!8?@#9!4?@!6?@!6?_!7?A#21!8?o#47FFFJ$#34!14?_#116_WIW[[#32O#18C#11!6?G!4?G#8!5?@!8?O$#19!15?C#74A!4?G#65A#134!6?A???OA#71!6?A!6?G#34_$#71!15?G#115CDEBAF#108@#144!6?@!4?@#14!6?C#74G!4?A#19C$#113!15?O#119_o__#106_#41!8?C#131_??_#39C#109!6?@#115@?AFF#33@#114O$#33!16?@#112?@?@#141!9?G??G#117!8?EEC$#145!30?A??E#32!8?O#119O!5_$#147!30?@??@#116!9?GWWW[$#143!30?C?G#112!10?@@$#136!30?O#142wo#106!10?_$#146!31?CC$#150!31?AA$#165!31?@#163@-#44O___#21~#2~#6!8~{{{[{{{}!8~W??{!9~!6{s!5~^~~#2~#21~#44_?O_$#45m][^#30!10?!6A#8A#37!9?@_?@#8!9?A#30!6A#5!5?_#45!4?]}n]$#46@@B#105!11?@#119!5@#35@#5!9?_#39OO#35!10?@#119!5@#9G#46!10?@@?@$#9!17?_???@!8?E??A#105!15?@$#132!31?GG$#141!31?AA$#136!31?C#11_$#142!31?@#139C$#145!32?@-#44BJBBC#48C?C??C#9!5?@#5@??@?@!7?@@#38??_#30__#48???C?C!8?C!6?C#44KFFJF$#46G?_#49?A?C?CC?!10C?!5C?!12C?C?!8C?!6C?A#45?_#172_o$o_#1???@#3!25A?AAA?!8A?!4A?!8A#2@#31_#46???G$#45C#43S[{x!26wowwWOW!21wWPwWS$#15!5?A#6!10@??@@?@?!7@??!12@?@?@?!9@#15A$#48!21?C!5?C#44???G???G#4!8?A!4?A#38!8?_$#4!31?A#2???A#5!8?@?@?@-#172!64N-\
\ No newline at end of file
diff --git a/alacritty_terminal/tests/sixel/testimage_libsixel.rgba b/alacritty_terminal/tests/sixel/testimage_libsixel.rgba
new file mode 100644
index 00000000..a9e1d6c7
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/testimage_libsixel.rgba
diff --git a/alacritty_terminal/tests/sixel/testimage_libsixel.sixel b/alacritty_terminal/tests/sixel/testimage_libsixel.sixel
new file mode 100644
index 00000000..7063a4b0
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/testimage_libsixel.sixel
@@ -0,0 +1 @@
+Pq"1;1;64;64#0;2;0;0;0#1;2;16;3;0#2;2;25;6;0#3;2;25;9;0#4;2;28;16;0#5;2;28;19;0#6;2;50;19;6#7;2;91;16;0#8;2;91;19;0#9;2;91;22;0#10;2;94;25;0#11;2;94;28;0#12;2;94;31;0#13;2;94;35;0#14;2;94;38;0#15;2;94;41;0#16;2;94;44;0#17;2;94;47;0#18;2;94;50;0#19;2;97;53;0#20;2;97;56;0#21;2;97;60;0#22;2;97;63;0#23;2;63;44;0#24;2;16;0;0#25;2;88;19;0#26;2;88;25;0#27;2;88;28;0#28;2;91;31;0#29;2;88;35;0#30;2;91;38;0#31;2;91;41;0#32;2;91;44;0#33;2;91;50;0#34;2;94;53;0#35;2;91;56;0#36;2;91;60;0#37;2;25;13;0#38;2;16;16;16#39;2;50;50;50#40;2;78;47;41#41;2;82;50;41#42;2;82;53;41#43;2;82;56;41#44;2;82;60;41#45;2;82;63;41#46;2;82;66;41#47;2;82;69;41#48;2;53;53;53#49;2;28;28;28#50;2;66;66;66#51;2;56;56;56#52;2;38;38;38#53;2;6;9;13#54;2;6;6;6#55;2;63;63;63#56;2;3;6;6#57;2;6;13;16#58;2;19;16;13#59;2;35;13;9#60;2;63;25;6#61;2;47;16;9#62;2;28;22;13#63;2;50;25;6#64;2;25;22;13#65;2;85;31;0#66;2;75;28;3#67;2;9;13;16#68;2;41;25;9#69;2;9;16;16#70;2;35;50;63#71;2;72;85;91#72;2;47;47;47#73;2;6;28;41#74;2;97;97;97#75;2;53;69;82#76;2;19;19;13#77;2;94;97;97#78;2;56;38;6#79;2;44;44;44#80;2;19;19;19#81;2;6;22;35#82;2;85;94;97#83;2;6;25;38#84;2;69;44;3#85;2;6;44;69#86;2;47;78;97#87;2;0;60;94#88;2;13;66;97#89;2;88;50;0#90;2;44;28;9#91;2;3;63;97#92;2;41;75;97#93;2;22;22;22#94;2;35;35;35#95;2;31;31;31#0~^NF!56BFN^~$#38?_#24O#25!8O#10??GGG#11!4G#12GGG#13GGG#14!4G#31!6O#17GGGWOOO#33OOO#34!4O#21GGG#22!4GWWWO#37O#38_$#39??_#6G#41!13_#42!8_#43!7_#44!8_#45!8_#46!7_#47!6_#48_$#40???_#7GG#8GGG#9GGWWO#26!4O#27OOO#3!12C#4!19C#5!7C#1C#23G$#1!4?C#2!16C#28!4O#29OOO#30OO#15GGG#16GGG#32OOO#18?GGG#19GG#20!5G#35OOO#36!4O-#50]^^^N!54FN^^^]$#55!4_#38_#53O!52_O#38_#55!4_$#49@#52???O#51G#48!52G#51G#52O#49???@$#56!5?_#54!52O#56_-#51!4o#38}#56~#57!20~^B!8?B^!20~#56~#38}#51!4o$#55!4N#53@#59!21?_??!6@??_#53!21?@#55!4N$#9!27?!10_$#25!27?O!8?O$#38!27?C!8?C$#61!27?G!8?G$#7!28?C!6EC$#8!28?!8W$#58!28?@!6?@$#60!28?A!6?A-#48!4{#38~#56~#57!18~N@#10!12E#57@N!18~#56~#38~#48!4{$#51!4B#60!20?_?@#9!10@#60@?_#51!20?!4B$#62!24?O#6C!5?OO!5?C#59O$#11!25?o!4wW??W!4wo$#26!25?G!5?GG!5?G$#38!25?A!5?__!5?A$#28!30?_??_-#39!4o#38~#56~#57!15~^F!6?_{^^{_!6?B^!15~#56~#38~#39!4o$#48!4N#38!17?_?@#12!6B!4?!6B#38@?_#48!17?!4N$#14!22?!6_!8?!6_$#66!22?O!6?C!4?C!6?O$#62!22?G#13W!4[K!6?K!4[W#62G$#63!23?A!4?_!6?_!4?A$#65!23?C#29!4?O!6?O#65!4?C$#67!29?O!4?O!6?C$#68!29?G!4?G$#60!30?@??@$#64!30?A??A$#69!31?__-#39!4B#38~#56~#57!13~N@!6?w}NB??BN}w!6?@N!13~#56~#38~#39!4B$#72!4{#76!15?O#67A!5?_#31@!8?@#66G!5?G#76O#72!15?!4{$#78!19?_#68C!5?O#60A!8?A#67_!5?A#78_$#16!20?O!5W#65G#62C!8?C#68O!5?C$#17!20?!5_#32_#38??@!6?@#15?!5EC$#66!20?G#15C!5E#69??O!4?O#14??!5@#29A$!21?A#14!5@#70??_?@@?_#16???!5WO$#63!21?@#73!8?C??C#32!4?_#17!5_$#74!30?_{{_#63!8?@$#75!30?G??G$#77!30?O??O$#71!31?AA-#52!4_#80~#56~#57!10~^F!6?o{~~@!6?@~~{o!6?F^!10~#56~#80~#52!4_$#79!4^#67!12?_?@#17A!5B#83???_!6?a#78??@!7?O#79!13?!4^$#76!17?G!7?A#85??S!6?S#38??A#84C!5?C#33_$#78!17?O!7?@#87??G!6?G#17???!5BA#67@?_$#33!17?_#84C!5?C#81???A#71@O??O@#62!4?G#18!5KG#76G$#18!18?G!5K#62G#82!4?AG??GA#89!5?O#19!5O$!18?!5O#89O#86!5?C!4?C#90!5?_#20!5_$!18?!5_#90_#88!5?W!4?W#32!9?@#68A$!18?A#32@#91!9?_!4?_$#74!30?B^^B$#77!30?C__C$#92!30?_??_-#52!4~#80N#56~#57!8~NB!5?_w}!5~o!4?o!5~}w_!5?BN!8~#56~#80N#52!4~$#93!4?o#69!9?O#78G!6?A#67@#69!5?G!4?G!5?@!8?O#93!9?o$#90!14?_#35O!4?_#62O#34@#73!6?C_??_C#78!6?A!6?G#90_$#22!15?!5_#76??C#85!6?AO??OA#33!6?@#20B!4FC#35O$#64!15?C#20C!4FB#87!7?@!4?@#76!6?C#21C!5W#64C$#21!16?!5WC#88!8?@CC@#84!8?G!4?A$!16?A!4?G#91!8?MwwM#62!8?O#89_#22!5_$#68!16?@#92!14?AA#68!14?@$#71!31?@#82@-#52!4@#93~#56~#57!8~!7{!9~}??{!9~!7{!8~#56~#93~#52!4@$#94!4]#64!10?!6A#69A#83!9?@#69__A!9?A#64!6A#94!10?!4]$#95!4_#89!10?@#22!5@#90@#73!10?OO#81@#90!9?@#22!5@#89@#95!10?!4_$#85!31?KK$#91!31?BB-#95FfFFC#38A#54!52A#38A#95CFFfF$#94O?_#72?A?!52C?A#94?_?O$#0_#49WWwx!54wxwWW#0_$#52G#56!4?@#57!52@#56@#52!4?G$#79!5?C!52?C-#0!64N\
\ No newline at end of file
diff --git a/alacritty_terminal/tests/sixel/testimage_ppmtosixel.rgba b/alacritty_terminal/tests/sixel/testimage_ppmtosixel.rgba
new file mode 100644
index 00000000..902b150d
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/testimage_ppmtosixel.rgba
diff --git a/alacritty_terminal/tests/sixel/testimage_ppmtosixel.sixel b/alacritty_terminal/tests/sixel/testimage_ppmtosixel.sixel
new file mode 100644
index 00000000..951f6028
--- /dev/null
+++ b/alacritty_terminal/tests/sixel/testimage_ppmtosixel.sixel
@@ -0,0 +1,77 @@
+�0;0;8q"1;1
+#0;2;0;0;0#1;2;49;49;49#2;2;28;28;28#3;2;14;15;16#4;2;12;12;12#5;2;95;38;0#6;2;61;61;61#7;2;100;100;100#8;2;90;33;0#9;2;59;17;8#10;2;53;22;11#11;2;9;9;9#12;2;36;21;12#13;2;52;72;81#14;2;94;29;1#15;2;96;51;0#16;2;96;45;0#17;2;26;24;13#18;2;54;54;54#19;2;98;62;0#20;2;33;33;33#21;2;38;38;38#22;2;66;66;66#23;2;51;51;51#24;2;29;29;29#25;2;93;20;1#26;2;95;36;0#27;2;97;58;0#28;2;93;59;0#29;2;67;31;5#30;2;95;52;1#31;2;44;44;44#32;2;4;6;8#33;2;56;56;56#34;2;35;35;35#35;2;40;40;40#36;2;8;14;17#37;2;52;52;52#38;2;34;23;16#39;2;91;43;0#40;2;31;31;31#41;2;19;18;16#42;2;93;24;1#43;2;93;18;1#44;2;95;40;0#45;2;89;24;1#46;2;95;35;0#47;2;97;56;0#48;2;70;81;87#49;2;83;64;41#50;2;89;22;1#51;2;85;39;2#52;2;82;58;41#53;2;74;28;4#54;2;97;55;0#55;2;29;21;16#56;2;45;45;45#57;2;94;31;0#58;2;57;57;57#59;2;36;36;36#60;2;42;42;42#61;2;80;39;3#62;2;40;21;13#63;2;33;33;33#64;2;87;17;2#65;2;7;13;16#66;2;32;18;13#67;2;13;13;13#68;2;83;62;41#69;2;93;35;0#70;2;62;62;62#71;2;47;47;47#72;2;15;15;15#73;2;59;59;59#74;2;22;22;22#75;2;93;53;1#76;2;94;28;1#77;2;96;50;0#78;2;51;27;14#79;2;64;64;64#80;2;48;48;48#81;2;87;95;100#82;2;27;27;27#83;2;95;33;0#84;2;48;64;60#85;2;60;60;60#86;2;88;55;21#87;2;77;88;95#88;2;90;34;0#89;2;11;14;16#90;2;97;54;0#91;2;96;48;0#92;2;98;65;0#93;2;27;15;14#94;2;53;53;53#95;2;38;38;38#96;2;44;27;16#97;2;93;22;1#98;2;76;46;14#99;2;96;44;0#100;2;94;24;0#101;2;65;65;65#102;2;95;39;0#103;2;98;61;0#104;2;6;11;13#105;2;50;50;50#106;2;29;29;29#107;2;62;62;62#108;2;12;15;16#109;2;100;59;0#110;2;68;30;5#111;2;98;99;100#112;2;43;43;43#113;2;11;16;16#114;2;76;38;4#115;2;94;41;0#116;2;55;55;55#117;2;71;32;5#118;2;34;34;34#119;2;39;39;39#120;2;2;62;100#121;2;3;5;6#122;2;94;26;1#123;2;93;21;1#124;2;96;43;0#125;2;98;65;0#126;2;51;51;51#127;2;98;59;0#128;2;91;44;0#129;2;30;30;30#130;2;83;61;41#131;2;97;57;0#132;2;89;49;21#133;2;65;32;6#134;2;95;33;0#135;2;44;44;44#136;2;56;56;56#137;2;35;35;35#138;2;91;30;1#139;2;41;41;41#140;2;52;18;9#141;2;3;60;97#142;2;67;26;6#143;2;96;41;0#144;2;32;32;32#145;2;79;38;3#146;2;93;62;0#147;2;8;14;17#148;2;36;14;12#149;2;95;37;0#150;2;95;32;0#151;2;22;16;15#152;2;5;42;64#153;2;46;46;46#154;2;13;13;13#155;2;19;50;70#156;2;34;34;34#157;2;82;55;41#158;2;97;53;0#159;2;58;58;58#160;2;42;42;42#161;2;81;68;43#162;2;69;70;61#163;2;89;29;0#164;2;8;14;17#165;2;96;43;0#166;2;100;100;100#167;2;94;98;100#168;2;15;16;16#169;2;14;14;14#170;2;91;47;0#171;2;63;63;63#172;2;94;29;0#173;2;47;47;47#174;2;26;26;26#175;2;68;85;95#176;2;95;34;0#177;2;7;24;35#178;2;60;60;60#179;2;44;44;44#180;2;7;7;7#181;2;91;53;1#182;2;81;50;41#183;2;94;25;1#184;2;96;47;0#185;2;96;42;0#186;2;98;64;0#187;2;53;53;53#188;2;37;37;37#189;2;94;47;0#190;2;66;36;6#191;2;16;17;17#192;2;17;29;32#193;2;65;65;65
+#0!64@$
+#0!64A$
+#0!4C#123C#43!3C#100!6C#172!7C#69!6C#115!6C#189!7C#30!5C#158C#109!6C#92!7C#109C#0!4C$
+#0!3G#43!3G#25!2G#123G#97!2G#42G#183!2G#122G#76!2G#172G#57!2G#150G#83G#176G#46G#26G#149G#5G#102G#44!2G#143G#124G#165G#99G#16!2G#184G#91!2G#77G#15G#158!2G#90!2G#54G#47G#131G#27G#127G#103!2G#19!2G#186G#125G#92!5G#0!3G$
+#0!2O#64!6O#50!4O#45!4O#163!4O#138O#8!3O#88!4O#69!2O#39!5O#128!2O#170!6O#75!4O#181O#75O#181O#28!5O#146!6O#28O#0!2O$
+#0_#76_#162_#182!12_#157!10_#52!7_#130!5_#68!3_#49!8_#120!2_#161!11_#162_#76_#0_$
+-
+#88@#43@#22!60@#43@#88@$
+#48A#101!62A#48A$
+#22C#193!62C#22C$
+#193G#79!4G#136G#18!52G#136G#79!4G#193G$
+#171!4O#21O#11O#180!52O#11O#119O#171!4O$
+#70!4_#169_#121_#104!52_#121_#169_#70!4_$
+-
+#107!4@#4@#32@#147!22@#151@#148!6@#151@#147!22@#32@#4@#107!4@$
+#6!4A#154A#32A#147!22A#9A#43!6A#9A#147!22A#32A#154A#6!4A$
+#85!4C#154C#32C#147!21C#72C#43!8C#72C#147!21C#32C#154C#85!4C$
+#178!4G#154G#32G#147!21G#140G#25!8G#140G#147!21G#32G#154G#178!4G$
+#73!4O#67O#32O#147!21O#64O#123!8O#64O#164O#147!20O#32O#67O#73!4O$
+#159!4_#169_#32_#147!20_#66_#97!10_#66_#147!20_#32_#169_#159!4_$
+-
+#58!4@#169@#32@#147!20@#142@#42!10@#142@#147!20@#32@#169@#58!4@$
+#136!4A#169A#32A#147!19A#72A#183!12A#72A#147!19A#32A#169A#136!4A$
+#33!4C#72C#32C#147!19C#140C#122!12C#140C#147!19C#32C#72C#33!4C$
+#116!4G#72G#32G#147!18G#164G#45G#76!5G#45!2G#76!5G#45G#164G#147!18G#32G#72G#116!4G$
+#18!4O#72O#32O#147!18O#66O#14!6O#10!2O#14!6O#66O#147!18O#32O#72O#18!4O$
+#94!4_#72_#32_#147!18_#142_#57!5_#138_#72!2_#138_#57!5_#142_#147!18_#32_#72_#94!4_$
+-
+#187!4@#168@#32@#147!17@#191@#57@#150!5@#142@#147!2@#142@#150!5@#57@#41@#147!17@#32@#168@#187!4@$
+#37!4A#168A#32A#147!17A#10A#134!6A#93A#147!2A#93A#134!6A#10A#147!17A#32A#168A#37!4A$
+#126!4C#191C#32C#147!16C#164C#8C#46!5C#53C#147!4C#53C#46!5C#8C#164C#147!16C#32C#191C#126!4C$
+#23!4G#191G#32G#147!16G#12G#26!6G#62G#147!4G#62G#26!6G#12G#147!16G#32G#191G#23!4G$
+#105!4O#191O#32O#147!16O#110O#149!5O#88O#89O#147!4O#89O#88O#149!5O#110O#147!16O#32O#191O#105!4O$
+#1!4_#191_#32_#147!15_#41_#5_#102!5_#10_#147!2_#36!2_#147!2_#10_#102!6_#41_#147!15_#32_#191_#1!4_$
+-
+#80!4@#191@#32@#147!15@#10@#44!5@#115@#191@#147!2@#84@#80@#147!2@#191@#115@#44!5@#10@#147!15@#32@#191@#80!4@$
+#173!4A#191A#32A#147!14A#164A#51A#185!5A#133A#147!3A#127A#175A#147!3A#133A#185!5A#51A#89A#147!14A#32A#191A#173!4A$
+#71!4C#191C#32C#147!14C#12C#124!6C#55C#147!2C#192C#111C#7C#192C#147!2C#55C#124!6C#12C#147!14C#32C#191C#71!4C$
+#153!4G#41G#32G#147!14G#117G#99!5G#145G#147!3G#13G#166!2G#13G#147!3G#114G#99!5G#117G#147!14G#32G#41G#153!4G$
+#56!4O#41O#32O#147!13O#41O#99O#16!5O#62O#147!2O#36O#81O#166!2O#167O#127O#147!2O#96O#16!6O#41O#147!13O#32O#41O#56!4O$
+#135!4_#41_#32_#147!13_#78_#184!5_#128_#113_#147!2_#155_#7_#166!2_#7_#155_#147!2_#89_#128_#184!5_#78_#147!13_#32_#41_#135!4_$
+-
+#31!4@#41@#32@#147!12@#89@#128@#91!5@#78@#147!3@#175@#7@#166!2@#7@#190@#147!3@#78@#91!5@#170@#89@#147!12@#32@#41@#31!4@$
+#112!4A#41A#32A#147!12A#12A#77!6A#41A#147!2A#177A#87A#111A#166!2A#111A#87A#177A#147!2A#41A#77!6A#12A#147!12A#32A#41A#112!4A$
+#160!4C#41C#32C#147!12C#114C#15!5C#190C#147!3C#152C#78C#167C#7!2C#167C#78C#152C#147!3C#190C#15!5C#114C#147!12C#32C#41C#160!4C$
+#60!4G#41G#32G#147!11G#41G#158!6G#17G#147!3G#141G#3G#81G#111!2G#81G#36G#141G#147!3G#38G#158!6G#41G#147!11G#32G#41G#60!4G$
+#139!4O#74O#32O#147!11O#190O#90!5O#175O#164O#147!3O#152O#93O#175O#167!2O#82O#93O#152O#147!4O#61O#90!5O#175O#147!11O#32O#74O#139!4O$
+#35!4_#74_#32_#147!10_#89_#181_#54!5_#96_#147!4_#28_#120_#17_#167!2_#17_#120_#177_#147!4_#96_#54!5_#181_#89_#147!10_#32_#74_#35!4_$
+-
+#119!4@#74@#32@#147!10@#96@#47!5@#181@#108@#147!4@#36@#141@#169@#87!2@#169@#141@#36@#147!4@#113@#181@#47!5@#96@#147!10@#32@#74@#119!4@$
+#21!4A#74A#32A#147!10A#114A#27!5A#190A#147!6A#145A#120A#38!2A#120A#152A#147!6A#190A#27!5A#114A#147!10A#32A#74A#21!4A$
+#95!4C#74C#32C#147!9C#41C#127!5C#27C#41C#147!6C#75C#120C#93!2C#120C#185C#147!6C#41C#27C#127!5C#17C#147!9C#32C#74C#95!4C$
+#188!4G#74G#32G#147!9G#190G#103!5G#114G#147!7G#36G#141G#120!2G#141G#36G#147!7G#114G#103!5G#190G#147!9G#32G#74G#188!4G$
+#59!4O#74O#32O#147!8O#113O#28O#19!5O#38O#147!8O#86O#120!2O#132O#147!8O#38O#19!5O#28O#113O#147!8O#32O#74O#59!4O$
+#137!4_#74_#32_#147!8_#96_#186!5_#181_#164_#147!8_#88_#120!2_#138_#147!8_#164_#181_#186!5_#96_#147!8_#32_#74_#137!4_$
+-
+#34!4@#74@#32@#147!8@#98@#92!5@#141@#147!9@#177@#120!2@#177@#147!9@#141@#125!5@#98@#147!8@#32@#74@#34!4@$
+#118!4A#74A#32A#147!7A#164A#17!6A#113A#147!9A#36A#141!2A#36A#147!9A#113A#17!6A#164A#147!7A#32A#74A#118!4A$
+#20!4C#74C#32C#147!25C#29C#110C#147!25C#32C#74C#20!4C$
+#63!4G#74G#32G#147!25G#152!2G#147!25G#32G#74G#63!4G$
+#144!4O#74O#32O#147!25O#124!2O#147!25O#32O#74O#144!4O$
+#40!4_#74_#32_#147!25_#54!2_#147!25_#32_#74_#40!4_$
+-
+#129!4@#82@#121@#65!52@#121@#82@#129!4@$
+#24!4A#71A#168A#11!52A#168A#71A#24!4A$
+#129C#106!3C#129C#160C#179!52C#160C#129C#106!3C#129C$
+#188G#2!62G#188G$
+#153O#82!62O#56O$
+#0_#160_#156_#82_#174!56_#82_#156_#139_#0_$
+-
+#0!64@$
+#0!64A$
+#0!64C$
+#0!64G$
+�