use super::parser::{Parser, is_regular, is_whitespace};
const MAX_DRAWN: usize = 4096;
const MAX_TOKEN: usize = 8;
const MAX_NAME: usize = 4096;
#[derive(Debug, Clone, PartialEq)]
pub(super) enum Drawn {
Name(Vec<u8>),
Long,
}
impl Drawn {
pub fn is(&self, key: &[u8]) -> bool {
match self {
Self::Name(name) => name == key,
Self::Long => key.len() > MAX_NAME / 3,
}
}
}
#[derive(Debug, Default, PartialEq)]
pub(super) struct Found {
pub postscript: bool,
pub drawn: Vec<Drawn>,
}
#[derive(Clone, Copy)]
enum State {
Between,
Comment,
String {
depth: usize,
escaped: bool,
},
Less,
Hex,
Token,
Name,
Image(End),
}
#[derive(Clone, Copy, PartialEq)]
enum End {
Nothing,
Space,
E,
Both,
}
pub(super) struct Operators {
state: State,
unclosed: bool,
unending: bool,
token: [u8; MAX_TOKEN],
token_len: usize,
name: Vec<u8>,
name_long: bool,
named: bool,
found: Found,
room: usize,
other: Option<Box<Operators>>,
}
impl Operators {
pub fn new() -> Self {
Self {
state: State::Between,
unclosed: false,
unending: false,
token: [0; MAX_TOKEN],
token_len: 0,
name: Vec::new(),
name_long: false,
named: false,
found: Found::default(),
room: MAX_DRAWN,
other: None,
}
}
fn fork(&self, unclosed: bool, unending: bool) -> Box<Self> {
Box::new(Self {
unclosed,
unending,
name: self.name.clone(),
name_long: self.name_long,
named: self.named,
room: self.room - self.found.drawn.len(),
..Self::new()
})
}
pub fn feed(&mut self, block: &[u8]) {
let mut pos = 0;
while pos < block.len() && !self.found.postscript {
let rest = &block[pos..];
pos += match self.state {
State::Between => self.between(rest),
State::Comment => {
let end = memchr::memchr2(b'\n', b'\r', rest);
self.leave(end, rest)
}
State::String { .. } => self.string(rest, false),
State::Less => {
self.state = match rest[0] {
b'<' => State::Between,
_ => State::Hex,
};
0
}
State::Hex => self.leave(memchr::memchr(b'>', rest), rest),
State::Token => {
let length = regular(rest);
let kept = length.min(MAX_TOKEN.saturating_sub(self.token_len));
let start = self.token_len.min(MAX_TOKEN);
self.token[start..start + kept].copy_from_slice(&rest[..kept]);
self.token_len = self.token_len.saturating_add(length);
if length < rest.len() {
self.end_token();
}
length
}
State::Name => {
let length = regular(rest);
self.name_more(&rest[..length]);
if length < rest.len() {
self.named = true;
self.state = State::Between;
}
length
}
State::Image(_) => self.image(rest),
};
}
}
fn leave(&mut self, end: Option<usize>, rest: &[u8]) -> usize {
if end.is_some() {
self.state = State::Between;
}
end.unwrap_or(rest.len())
}
fn name_more(&mut self, bytes: &[u8]) {
let kept = bytes
.len()
.min((MAX_NAME + 1).saturating_sub(self.name.len()));
self.name.extend_from_slice(&bytes[..kept]);
self.name_long |= kept < bytes.len();
}
fn between(&mut self, rest: &[u8]) -> usize {
let mut pos = 0;
while let Some(&byte) = rest.get(pos) {
if is_regular(byte) {
let length = regular(&rest[pos..]);
if pos + length == rest.len() {
self.token_len = 0;
self.state = State::Token;
break;
}
self.operator(&rest[pos..pos + length]);
pos += length;
if self.found.postscript || !matches!(self.state, State::Between) {
break;
}
continue;
}
pos += 1;
match byte {
b'%' => self.state = State::Comment,
b'(' if !self.unclosed => {
self.state = State::String {
depth: 1,
escaped: false,
};
pos += self.string(&rest[pos..], true);
}
b'<' => self.state = State::Less,
b'/' => {
self.name.clear();
self.name.push(b'/');
self.name_long = false;
let length = regular(&rest[pos..]);
self.name_more(&rest[pos..pos + length]);
pos += length;
if pos == rest.len() {
self.state = State::Name;
} else {
self.named = true;
}
}
_ => {}
}
if !matches!(self.state, State::Between) {
break;
}
}
pos
}
fn string(&mut self, rest: &[u8], opening: bool) -> usize {
let State::String {
mut depth,
mut escaped,
} = self.state
else {
return 0;
};
let mut pos = usize::from(escaped && !rest.is_empty());
escaped &= rest.is_empty();
while let Some(length) = memchr::memchr3(b'\\', b'(', b')', &rest[pos..]) {
pos += length + 1;
match rest[pos - 1] {
b'\\' if pos == rest.len() => escaped = true,
b'\\' => pos += 1,
b'(' => depth += 1,
_ => depth -= 1,
}
if depth == 0 {
self.other = None;
self.state = State::Between;
return pos;
}
}
self.state = State::String { depth, escaped };
if opening {
self.other = Some(self.fork(true, self.unending));
}
if let Some(other) = &mut self.other {
other.feed(rest);
}
rest.len()
}
fn image(&mut self, rest: &[u8]) -> usize {
let State::Image(mut end) = self.state else {
return 0;
};
for (index, &byte) in rest.iter().enumerate() {
end = match (end, byte) {
(End::Both, _) if !is_regular(byte) => {
self.end_image();
return index;
}
(End::Space, b'E') => End::E,
(End::E, b'I') => End::Both,
_ if is_whitespace(byte) => End::Space,
_ => End::Nothing,
};
}
self.state = State::Image(end);
if let Some(other) = &mut self.other {
other.feed(rest);
}
rest.len()
}
fn end_image(&mut self) {
self.other = None;
self.token[..2].copy_from_slice(b"EI");
self.token_len = 2;
self.state = State::Token;
}
fn end_token(&mut self) {
self.state = State::Between;
let token = self.token;
self.operator(&token[..self.token_len.min(MAX_TOKEN)]);
}
fn operator(&mut self, token: &[u8]) {
let named = std::mem::take(&mut self.named);
match token {
b"PS" => self.found.postscript = true,
b"Do" if named && self.found.drawn.len() < self.room => {
let name = if self.name_long {
Drawn::Long
} else {
let mut parser = Parser::new(&self.name, 0, usize::MAX);
Drawn::Name(
parser
.name()
.map_or(Vec::new(), |name| name.text().to_vec()),
)
};
self.found.drawn.push(name);
}
b"ID" if !self.unending => {
self.state = State::Image(End::Nothing);
self.other = Some(self.fork(self.unclosed, true));
}
_ => {}
}
}
pub fn finish(mut self) -> Found {
if self.found.postscript {
return self.found;
}
match self.state {
State::Token => self.end_token(),
State::Image(End::Both) => {
self.end_image();
self.end_token();
}
_ => {}
}
if let State::String { .. } | State::Image(_) = self.state
&& let Some(other) = self.other.take()
{
let rest = other.finish();
self.found.postscript = rest.postscript;
self.found.drawn.extend(rest.drawn);
}
self.found
}
}
fn regular(bytes: &[u8]) -> usize {
let end = bytes.iter().position(|&byte| !is_regular(byte));
end.unwrap_or(bytes.len())
}
pub(super) fn scan(content: &[u8]) -> Found {
let mut operators = Operators::new();
operators.feed(content);
operators.finish()
}
#[cfg(test)]
mod tests {
use memchr::memmem;
use super::*;
fn for_each_operator(
content: &[u8],
mut visit: impl FnMut(&[u8], Option<&[u8]>) -> bool,
) -> bool {
let mut unclosed_string = false;
let mut last_name: Option<Vec<u8>> = None;
let mut pos = 0;
while let Some(&byte) = content.get(pos) {
match byte {
b'%' => {
pos += memchr::memchr2(b'\n', b'\r', &content[pos..]).unwrap_or(content.len())
}
b'(' if unclosed_string => pos += 1,
b'(' => {
let start = pos;
let mut depth = 0usize;
while let Some(&inner) = content.get(pos) {
pos += 1;
match inner {
b'\\' => pos += 1,
b'(' => depth += 1,
b')' => depth -= 1,
_ => {}
}
if depth == 0 {
break;
}
}
if depth > 0 {
unclosed_string = true;
pos = start + 1;
}
}
b'<' if content.get(pos + 1) != Some(&b'<') => {
pos += memchr::memchr(b'>', &content[pos..]).unwrap_or(content.len());
}
_ if is_regular(byte) => {
let length = content[pos..]
.iter()
.take_while(|&&b| is_regular(b))
.count();
let token = &content[pos..pos + length];
if visit(token, last_name.take().as_deref()) {
return true;
}
pos += length;
if token == b"ID" {
let end = memmem::find_iter(&content[pos..], b"EI").find(|&at| {
let before = content[pos + at - 1];
let after = content.get(pos + at + 2);
is_whitespace(before) && after.is_none_or(|&b| !is_regular(b))
});
pos += end.unwrap_or(0);
}
}
b'/' => {
let mut parser = Parser::new(content, pos, usize::MAX);
last_name = parser.name().map(|name| name.text().to_vec());
pos = parser.pos;
}
_ => pos += 1,
}
}
false
}
fn in_one_piece(content: &[u8]) -> Found {
let mut drawn = Vec::new();
let postscript = for_each_operator(content, |token, name| {
if token == b"Do"
&& let Some(name) = name
&& drawn.len() < MAX_DRAWN
{
drawn.push(Drawn::Name(name.to_vec()));
}
token == b"PS"
});
Found { postscript, drawn }
}
fn in_blocks(content: &[u8], size: usize) -> Found {
let mut operators = Operators::new();
for block in content.chunks(size) {
operators.feed(block);
}
operators.finish()
}
fn drawn(content: &[u8]) -> Vec<Drawn> {
scan(content).drawn
}
#[test]
fn operators_and_their_names() {
assert!(scan(b"BT (text) Tj ET\n(1 2 moveto) PS\n").postscript);
assert!(scan(b"(x)PS").postscript);
assert!(!scan(b"(PS) Tj <5053> Tj /PS gs % PS\nPSx EPS BT ET").postscript);
assert_eq!(
drawn(b"q /A Do Q /B#20C (s) Do Do"),
[Drawn::Name(b"A".to_vec()), Drawn::Name(b"B C".to_vec())]
);
assert_eq!(drawn(b"(/A Do) Tj"), []);
for hidden in [
&b"BI /W 1 /H 1 ID (\x00 EI (x) PS"[..],
b"BI /W 1 /H 1 ID \x00) EI (x) PS",
b"( (x) PS",
b"BI ID ( (x) PS",
b"( BI ID (x) PS",
] {
assert!(scan(hidden).postscript, "{hidden:?}");
}
}
#[test]
fn long_tokens_and_names_are_not_kept() {
let mut content = b"PS".repeat(4096);
content.extend_from_slice(b" /");
content.extend(vec![b'n'; MAX_NAME + 1]);
content.extend_from_slice(b" Do");
assert_eq!(
scan(&content),
Found {
postscript: false,
drawn: vec![Drawn::Long],
}
);
assert!(Drawn::Long.is(&vec![b'n'; MAX_NAME + 1]));
assert!(!Drawn::Long.is(b"n"));
}
fn streams() -> impl Iterator<Item = Vec<u8>> {
const PIECES: [&[u8]; 40] = [
b"(", b")", b"\\", b"(a)", b"((b)c)", b"<", b"<<", b">", b">>", b"<41>", b"%", b"\n",
b"\r", b" ", b"/", b"/A", b"/B#20C", b"/#", b"Do", b"PS", b"ID", b"EI", b"BI", b"E",
b"I", b"D", b"P", b"S", b"o", b"q", b"\0", b"\t", b"[", b"]", b"{", b"12", b"/Do",
b"/PS", b" EI ", b"x",
];
let mut seed = 0x2545_F491_4F6C_DD1Du64;
let mut below = move |bound: usize| {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
(seed % bound as u64) as usize
};
(0..20_000).map(move |_| {
let mut stream = Vec::new();
for _ in 0..below(24) {
stream.extend_from_slice(PIECES[below(PIECES.len())]);
if below(3) == 0 {
stream.push(b' ');
}
}
stream
})
}
#[test]
fn blocks_of_any_size_read_as_one_piece() {
for stream in streams() {
let expected = in_one_piece(&stream);
for size in [1, 2, 3, 5, 7, 16, usize::MAX] {
assert_eq!(
in_blocks(&stream, size),
expected,
"{:?} in blocks of {size}",
String::from_utf8_lossy(&stream)
);
}
}
}
}