miniserde/json/
de.rs

1use self::Event::*;
2use crate::de::{Deserialize, Map, Seq, Visitor};
3use crate::error::{Error, Result};
4use crate::ptr::NonuniqueBox;
5use alloc::vec::Vec;
6use core::char;
7use core::ptr::NonNull;
8use core::str;
9
10/// Deserialize a JSON string into any deserializable type.
11///
12/// ```rust
13/// use miniserde::{json, Deserialize};
14///
15/// #[derive(Deserialize, Debug)]
16/// struct Example {
17///     code: u32,
18///     message: String,
19/// }
20///
21/// fn main() -> miniserde::Result<()> {
22///     let j = r#" {"code": 200, "message": "reminiscent of Serde"} "#;
23///
24///     let out: Example = json::from_str(&j)?;
25///     println!("{:?}", out);
26///
27///     Ok(())
28/// }
29/// ```
30pub fn from_str<T>(j: &str) -> Result<T>
31where
32    T: Deserialize,
33{
34    let mut out = None;
35    from_str_impl(j, T::begin(&mut out))?;
36    out.ok_or(Error)
37}
38
39struct Deserializer<'a, 'b> {
40    input: &'a [u8],
41    pos: usize,
42    buffer: Vec<u8>,
43    stack: Vec<(NonNull<dyn Visitor>, Layer<'b>)>,
44}
45
46enum Layer<'a> {
47    Seq(NonuniqueBox<dyn Seq + 'a>),
48    Map(NonuniqueBox<dyn Map + 'a>),
49}
50
51impl<'a, 'b> Drop for Deserializer<'a, 'b> {
52    fn drop(&mut self) {
53        // Drop layers in reverse order.
54        while !self.stack.is_empty() {
55            self.stack.pop();
56        }
57    }
58}
59
60fn from_str_impl(j: &str, visitor: &mut dyn Visitor) -> Result<()> {
61    let visitor = NonNull::from(visitor);
62    let mut visitor = unsafe { extend_lifetime!(visitor as NonNull<dyn Visitor>) };
63    let mut de = Deserializer {
64        input: j.as_bytes(),
65        pos: 0,
66        buffer: Vec::new(),
67        stack: Vec::new(),
68    };
69
70    'outer: loop {
71        let visitor_mut = unsafe { &mut *visitor.as_ptr() };
72        let layer = match de.event()? {
73            Null => {
74                visitor_mut.null()?;
75                None
76            }
77            Bool(b) => {
78                visitor_mut.boolean(b)?;
79                None
80            }
81            Negative(n) => {
82                visitor_mut.negative(n)?;
83                None
84            }
85            Nonnegative(n) => {
86                visitor_mut.nonnegative(n)?;
87                None
88            }
89            Float(n) => {
90                visitor_mut.float(n)?;
91                None
92            }
93            Str(s) => {
94                visitor_mut.string(s)?;
95                None
96            }
97            SeqStart => {
98                let seq = visitor_mut.seq()?;
99                Some(Layer::Seq(NonuniqueBox::from(seq)))
100            }
101            MapStart => {
102                let map = visitor_mut.map()?;
103                Some(Layer::Map(NonuniqueBox::from(map)))
104            }
105        };
106
107        let mut accept_comma;
108        let mut layer = match layer {
109            Some(layer) => {
110                accept_comma = false;
111                layer
112            }
113            None => match de.stack.pop() {
114                Some(frame) => {
115                    accept_comma = true;
116                    visitor = frame.0;
117                    frame.1
118                }
119                None => break 'outer,
120            },
121        };
122
123        loop {
124            match de.parse_whitespace().unwrap_or(b'\0') {
125                b',' if accept_comma => {
126                    de.bump();
127                    break;
128                }
129                close @ (b']' | b'}') => {
130                    de.bump();
131                    match &mut layer {
132                        Layer::Seq(seq) if close == b']' => seq.finish()?,
133                        Layer::Map(map) if close == b'}' => map.finish()?,
134                        _ => return Err(Error),
135                    }
136                    let Some(frame) = de.stack.pop() else {
137                        break 'outer;
138                    };
139                    accept_comma = true;
140                    visitor = frame.0;
141                    layer = frame.1;
142                }
143                _ => {
144                    if accept_comma {
145                        return Err(Error);
146                    } else {
147                        break;
148                    }
149                }
150            }
151        }
152
153        let outer = visitor;
154        match layer {
155            Layer::Seq(mut seq) => {
156                let element = seq.element()?;
157                let next = NonNull::from(element);
158                visitor = unsafe { extend_lifetime!(next as NonNull<dyn Visitor>) };
159                de.stack.push((outer, Layer::Seq(seq)));
160            }
161            Layer::Map(mut map) => {
162                match de.parse_whitespace() {
163                    Some(b'"') => de.bump(),
164                    _ => return Err(Error),
165                }
166                let key = de.parse_str()?;
167                let entry = map.key(key)?;
168                let next = NonNull::from(entry);
169                visitor = unsafe { extend_lifetime!(next as NonNull<dyn Visitor>) };
170                match de.parse_whitespace() {
171                    Some(b':') => de.bump(),
172                    _ => return Err(Error),
173                }
174                de.stack.push((outer, Layer::Map(map)));
175            }
176        }
177    }
178
179    match de.parse_whitespace() {
180        Some(_) => Err(Error),
181        None => Ok(()),
182    }
183}
184
185enum Event<'a> {
186    Null,
187    Bool(bool),
188    Str(&'a str),
189    Negative(i64),
190    Nonnegative(u64),
191    Float(f64),
192    SeqStart,
193    MapStart,
194}
195
196macro_rules! overflow {
197    ($a:ident * 10 + $b:ident, $c:expr) => {
198        match $c {
199            c => $a >= c / 10 && ($a > c / 10 || $b > c % 10),
200        }
201    };
202}
203
204impl<'a, 'b> Deserializer<'a, 'b> {
205    fn next(&mut self) -> Option<u8> {
206        if self.pos < self.input.len() {
207            let ch = self.input[self.pos];
208            self.pos += 1;
209            Some(ch)
210        } else {
211            None
212        }
213    }
214
215    fn next_or_nul(&mut self) -> u8 {
216        self.next().unwrap_or(b'\0')
217    }
218
219    fn peek(&mut self) -> Option<u8> {
220        if self.pos < self.input.len() {
221            Some(self.input[self.pos])
222        } else {
223            None
224        }
225    }
226
227    fn peek_or_nul(&mut self) -> u8 {
228        self.peek().unwrap_or(b'\0')
229    }
230
231    fn bump(&mut self) {
232        self.pos += 1;
233    }
234
235    fn parse_str(&mut self) -> Result<&str> {
236        fn result(bytes: &[u8]) -> &str {
237            // The deserialization input came in as &str with a UTF-8 guarantee,
238            // and the \u-escapes are checked along the way, so don't need to
239            // check here.
240            unsafe { str::from_utf8_unchecked(bytes) }
241        }
242
243        // Index of the first byte not yet copied into the scratch space.
244        let mut start = self.pos;
245        self.buffer.clear();
246
247        loop {
248            while self.pos < self.input.len() && !ESCAPE[usize::from(self.input[self.pos])] {
249                self.pos += 1;
250            }
251            if self.pos == self.input.len() {
252                return Err(Error);
253            }
254            match self.input[self.pos] {
255                b'"' => {
256                    if self.buffer.is_empty() {
257                        // Fast path: return a slice of the raw JSON without any
258                        // copying.
259                        let borrowed = &self.input[start..self.pos];
260                        self.pos += 1;
261                        return Ok(result(borrowed));
262                    } else {
263                        self.buffer.extend_from_slice(&self.input[start..self.pos]);
264                        self.pos += 1;
265                        return Ok(result(&self.buffer));
266                    }
267                }
268                b'\\' => {
269                    self.buffer.extend_from_slice(&self.input[start..self.pos]);
270                    self.pos += 1;
271                    self.parse_escape()?;
272                    start = self.pos;
273                }
274                _ => {
275                    return Err(Error);
276                }
277            }
278        }
279    }
280
281    fn next_or_eof(&mut self) -> Result<u8> {
282        self.next().ok_or(Error)
283    }
284
285    /// Parses a JSON escape sequence and appends it into the scratch space. Assumes
286    /// the previous byte read was a backslash.
287    fn parse_escape(&mut self) -> Result<()> {
288        let ch = self.next_or_eof()?;
289
290        match ch {
291            b'"' => self.buffer.push(b'"'),
292            b'\\' => self.buffer.push(b'\\'),
293            b'/' => self.buffer.push(b'/'),
294            b'b' => self.buffer.push(b'\x08'),
295            b'f' => self.buffer.push(b'\x0c'),
296            b'n' => self.buffer.push(b'\n'),
297            b'r' => self.buffer.push(b'\r'),
298            b't' => self.buffer.push(b'\t'),
299            b'u' => {
300                let c = match self.decode_hex_escape()? {
301                    0xDC00..=0xDFFF => {
302                        return Err(Error);
303                    }
304
305                    // Non-BMP characters are encoded as a sequence of
306                    // two hex escapes, representing UTF-16 surrogates.
307                    n1 @ 0xD800..=0xDBFF => {
308                        if self.next_or_eof()? != b'\\' {
309                            return Err(Error);
310                        }
311                        if self.next_or_eof()? != b'u' {
312                            return Err(Error);
313                        }
314
315                        let n2 = self.decode_hex_escape()?;
316
317                        if n2 < 0xDC00 || n2 > 0xDFFF {
318                            return Err(Error);
319                        }
320
321                        let n =
322                            ((u32::from(n1 - 0xD800) << 10) | u32::from(n2 - 0xDC00)) + 0x1_0000;
323
324                        match char::from_u32(n) {
325                            Some(c) => c,
326                            None => {
327                                return Err(Error);
328                            }
329                        }
330                    }
331
332                    n => match char::from_u32(u32::from(n)) {
333                        Some(c) => c,
334                        None => {
335                            return Err(Error);
336                        }
337                    },
338                };
339
340                self.buffer
341                    .extend_from_slice(c.encode_utf8(&mut [0_u8; 4]).as_bytes());
342            }
343            _ => {
344                return Err(Error);
345            }
346        }
347
348        Ok(())
349    }
350
351    fn decode_hex_escape(&mut self) -> Result<u16> {
352        let mut n = 0;
353        for _ in 0..4 {
354            n = match self.next_or_eof()? {
355                c @ b'0'..=b'9' => n * 16_u16 + u16::from(c - b'0'),
356                b'a' | b'A' => n * 16_u16 + 10_u16,
357                b'b' | b'B' => n * 16_u16 + 11_u16,
358                b'c' | b'C' => n * 16_u16 + 12_u16,
359                b'd' | b'D' => n * 16_u16 + 13_u16,
360                b'e' | b'E' => n * 16_u16 + 14_u16,
361                b'f' | b'F' => n * 16_u16 + 15_u16,
362                _ => {
363                    return Err(Error);
364                }
365            };
366        }
367        Ok(n)
368    }
369
370    fn parse_whitespace(&mut self) -> Option<u8> {
371        loop {
372            match self.peek() {
373                Some(b' ' | b'\n' | b'\t' | b'\r') => {
374                    self.bump();
375                }
376                other => {
377                    return other;
378                }
379            }
380        }
381    }
382
383    fn parse_ident(&mut self, ident: &[u8]) -> Result<()> {
384        for expected in ident {
385            match self.next() {
386                None => {
387                    return Err(Error);
388                }
389                Some(next) => {
390                    if next != *expected {
391                        return Err(Error);
392                    }
393                }
394            }
395        }
396        Ok(())
397    }
398
399    fn parse_integer(&mut self, nonnegative: bool, first_digit: u8) -> Result<Event> {
400        match first_digit {
401            b'0' => {
402                // There can be only one leading '0'.
403                match self.peek_or_nul() {
404                    b'0'..=b'9' => Err(Error),
405                    _ => self.parse_number(nonnegative, 0),
406                }
407            }
408            c @ b'1'..=b'9' => {
409                let mut res = u64::from(c - b'0');
410
411                loop {
412                    match self.peek_or_nul() {
413                        c @ b'0'..=b'9' => {
414                            self.bump();
415                            let digit = u64::from(c - b'0');
416
417                            // We need to be careful with overflow. If we can, try to keep the
418                            // number as a `u64` until we grow too large. At that point, switch to
419                            // parsing the value as a `f64`.
420                            if overflow!(res * 10 + digit, u64::MAX) {
421                                return self
422                                    .parse_long_integer(
423                                        nonnegative,
424                                        res,
425                                        1, // res * 10^1
426                                    )
427                                    .map(Float);
428                            }
429
430                            res = res * 10 + digit;
431                        }
432                        _ => {
433                            return self.parse_number(nonnegative, res);
434                        }
435                    }
436                }
437            }
438            _ => Err(Error),
439        }
440    }
441
442    fn parse_long_integer(
443        &mut self,
444        nonnegative: bool,
445        significand: u64,
446        mut exponent: i32,
447    ) -> Result<f64> {
448        loop {
449            match self.peek_or_nul() {
450                b'0'..=b'9' => {
451                    self.bump();
452                    // This could overflow... if your integer is gigabytes long.
453                    // Ignore that possibility.
454                    exponent += 1;
455                }
456                b'.' => {
457                    return self.parse_decimal(nonnegative, significand, exponent);
458                }
459                b'e' | b'E' => {
460                    return self.parse_exponent(nonnegative, significand, exponent);
461                }
462                _ => {
463                    return f64_from_parts(nonnegative, significand, exponent);
464                }
465            }
466        }
467    }
468
469    fn parse_number(&mut self, nonnegative: bool, significand: u64) -> Result<Event> {
470        match self.peek_or_nul() {
471            b'.' => self.parse_decimal(nonnegative, significand, 0).map(Float),
472            b'e' | b'E' => self.parse_exponent(nonnegative, significand, 0).map(Float),
473            _ => {
474                Ok(if nonnegative {
475                    Nonnegative(significand)
476                } else {
477                    let neg = (significand as i64).wrapping_neg();
478
479                    // Convert into a float if we underflow.
480                    if neg > 0 {
481                        Float(-(significand as f64))
482                    } else {
483                        Negative(neg)
484                    }
485                })
486            }
487        }
488    }
489
490    fn parse_decimal(
491        &mut self,
492        nonnegative: bool,
493        mut significand: u64,
494        mut exponent: i32,
495    ) -> Result<f64> {
496        self.bump();
497
498        let mut at_least_one_digit = false;
499        while let c @ b'0'..=b'9' = self.peek_or_nul() {
500            self.bump();
501            let digit = u64::from(c - b'0');
502            at_least_one_digit = true;
503
504            if overflow!(significand * 10 + digit, u64::MAX) {
505                // The next multiply/add would overflow, so just ignore all
506                // further digits.
507                while let b'0'..=b'9' = self.peek_or_nul() {
508                    self.bump();
509                }
510                break;
511            }
512
513            significand = significand * 10 + digit;
514            exponent -= 1;
515        }
516
517        if !at_least_one_digit {
518            return Err(Error);
519        }
520
521        match self.peek_or_nul() {
522            b'e' | b'E' => self.parse_exponent(nonnegative, significand, exponent),
523            _ => f64_from_parts(nonnegative, significand, exponent),
524        }
525    }
526
527    fn parse_exponent(
528        &mut self,
529        nonnegative: bool,
530        significand: u64,
531        starting_exp: i32,
532    ) -> Result<f64> {
533        self.bump();
534
535        let positive_exp = match self.peek_or_nul() {
536            b'+' => {
537                self.bump();
538                true
539            }
540            b'-' => {
541                self.bump();
542                false
543            }
544            _ => true,
545        };
546
547        // Make sure a digit follows the exponent place.
548        let mut exp = match self.next_or_nul() {
549            c @ b'0'..=b'9' => i32::from(c - b'0'),
550            _ => {
551                return Err(Error);
552            }
553        };
554
555        while let c @ b'0'..=b'9' = self.peek_or_nul() {
556            self.bump();
557            let digit = i32::from(c - b'0');
558
559            if overflow!(exp * 10 + digit, i32::MAX) {
560                return self.parse_exponent_overflow(nonnegative, significand, positive_exp);
561            }
562
563            exp = exp * 10 + digit;
564        }
565
566        let final_exp = if positive_exp {
567            starting_exp.saturating_add(exp)
568        } else {
569            starting_exp.saturating_sub(exp)
570        };
571
572        f64_from_parts(nonnegative, significand, final_exp)
573    }
574
575    // This cold code should not be inlined into the middle of the hot
576    // exponent-parsing loop above.
577    #[cold]
578    #[inline(never)]
579    fn parse_exponent_overflow(
580        &mut self,
581        nonnegative: bool,
582        significand: u64,
583        positive_exp: bool,
584    ) -> Result<f64> {
585        // Error instead of +/- infinity.
586        if significand != 0 && positive_exp {
587            return Err(Error);
588        }
589
590        while let b'0'..=b'9' = self.peek_or_nul() {
591            self.bump();
592        }
593        Ok(if nonnegative { 0.0 } else { -0.0 })
594    }
595
596    fn event(&mut self) -> Result<Event> {
597        let Some(peek) = self.parse_whitespace() else {
598            return Err(Error);
599        };
600        self.bump();
601        match peek {
602            b'"' => self.parse_str().map(Str),
603            digit @ b'0'..=b'9' => self.parse_integer(true, digit),
604            b'-' => {
605                let first_digit = self.next_or_nul();
606                self.parse_integer(false, first_digit)
607            }
608            b'{' => Ok(MapStart),
609            b'[' => Ok(SeqStart),
610            b'n' => {
611                self.parse_ident(b"ull")?;
612                Ok(Null)
613            }
614            b't' => {
615                self.parse_ident(b"rue")?;
616                Ok(Bool(true))
617            }
618            b'f' => {
619                self.parse_ident(b"alse")?;
620                Ok(Bool(false))
621            }
622            _ => Err(Error),
623        }
624    }
625}
626
627fn f64_from_parts(nonnegative: bool, significand: u64, mut exponent: i32) -> Result<f64> {
628    let mut f = significand as f64;
629    loop {
630        match POW10.get(exponent.unsigned_abs() as usize) {
631            Some(&pow) => {
632                if exponent >= 0 {
633                    f *= pow;
634                    if f.is_infinite() {
635                        return Err(Error);
636                    }
637                } else {
638                    f /= pow;
639                }
640                break;
641            }
642            None => {
643                if f == 0.0 {
644                    break;
645                }
646                if exponent >= 0 {
647                    return Err(Error);
648                }
649                f /= 1e308;
650                exponent += 308;
651            }
652        }
653    }
654    Ok(if nonnegative { f } else { -f })
655}
656
657// Clippy bug: https://github.com/rust-lang/rust-clippy/issues/5201
658#[allow(clippy::excessive_precision)]
659static POW10: [f64; 309] = [
660    1e000, 1e001, 1e002, 1e003, 1e004, 1e005, 1e006, 1e007, 1e008, 1e009, //
661    1e010, 1e011, 1e012, 1e013, 1e014, 1e015, 1e016, 1e017, 1e018, 1e019, //
662    1e020, 1e021, 1e022, 1e023, 1e024, 1e025, 1e026, 1e027, 1e028, 1e029, //
663    1e030, 1e031, 1e032, 1e033, 1e034, 1e035, 1e036, 1e037, 1e038, 1e039, //
664    1e040, 1e041, 1e042, 1e043, 1e044, 1e045, 1e046, 1e047, 1e048, 1e049, //
665    1e050, 1e051, 1e052, 1e053, 1e054, 1e055, 1e056, 1e057, 1e058, 1e059, //
666    1e060, 1e061, 1e062, 1e063, 1e064, 1e065, 1e066, 1e067, 1e068, 1e069, //
667    1e070, 1e071, 1e072, 1e073, 1e074, 1e075, 1e076, 1e077, 1e078, 1e079, //
668    1e080, 1e081, 1e082, 1e083, 1e084, 1e085, 1e086, 1e087, 1e088, 1e089, //
669    1e090, 1e091, 1e092, 1e093, 1e094, 1e095, 1e096, 1e097, 1e098, 1e099, //
670    1e100, 1e101, 1e102, 1e103, 1e104, 1e105, 1e106, 1e107, 1e108, 1e109, //
671    1e110, 1e111, 1e112, 1e113, 1e114, 1e115, 1e116, 1e117, 1e118, 1e119, //
672    1e120, 1e121, 1e122, 1e123, 1e124, 1e125, 1e126, 1e127, 1e128, 1e129, //
673    1e130, 1e131, 1e132, 1e133, 1e134, 1e135, 1e136, 1e137, 1e138, 1e139, //
674    1e140, 1e141, 1e142, 1e143, 1e144, 1e145, 1e146, 1e147, 1e148, 1e149, //
675    1e150, 1e151, 1e152, 1e153, 1e154, 1e155, 1e156, 1e157, 1e158, 1e159, //
676    1e160, 1e161, 1e162, 1e163, 1e164, 1e165, 1e166, 1e167, 1e168, 1e169, //
677    1e170, 1e171, 1e172, 1e173, 1e174, 1e175, 1e176, 1e177, 1e178, 1e179, //
678    1e180, 1e181, 1e182, 1e183, 1e184, 1e185, 1e186, 1e187, 1e188, 1e189, //
679    1e190, 1e191, 1e192, 1e193, 1e194, 1e195, 1e196, 1e197, 1e198, 1e199, //
680    1e200, 1e201, 1e202, 1e203, 1e204, 1e205, 1e206, 1e207, 1e208, 1e209, //
681    1e210, 1e211, 1e212, 1e213, 1e214, 1e215, 1e216, 1e217, 1e218, 1e219, //
682    1e220, 1e221, 1e222, 1e223, 1e224, 1e225, 1e226, 1e227, 1e228, 1e229, //
683    1e230, 1e231, 1e232, 1e233, 1e234, 1e235, 1e236, 1e237, 1e238, 1e239, //
684    1e240, 1e241, 1e242, 1e243, 1e244, 1e245, 1e246, 1e247, 1e248, 1e249, //
685    1e250, 1e251, 1e252, 1e253, 1e254, 1e255, 1e256, 1e257, 1e258, 1e259, //
686    1e260, 1e261, 1e262, 1e263, 1e264, 1e265, 1e266, 1e267, 1e268, 1e269, //
687    1e270, 1e271, 1e272, 1e273, 1e274, 1e275, 1e276, 1e277, 1e278, 1e279, //
688    1e280, 1e281, 1e282, 1e283, 1e284, 1e285, 1e286, 1e287, 1e288, 1e289, //
689    1e290, 1e291, 1e292, 1e293, 1e294, 1e295, 1e296, 1e297, 1e298, 1e299, //
690    1e300, 1e301, 1e302, 1e303, 1e304, 1e305, 1e306, 1e307, 1e308,
691];
692
693const CT: bool = true; // control character \x00..=\x1F
694const QU: bool = true; // quote \x22
695const BS: bool = true; // backslash \x5C
696const O: bool = false; // allow unescaped
697
698// Lookup table of bytes that must be escaped. A value of true at index i means
699// that byte i requires an escape sequence in the input.
700#[rustfmt::skip]
701static ESCAPE: [bool; 256] = [
702    //   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
703    CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, // 0
704    CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, CT, // 1
705     O,  O, QU,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 2
706     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 3
707     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 4
708     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, BS,  O,  O,  O, // 5
709     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 6
710     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 7
711     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 8
712     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // 9
713     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // A
714     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // B
715     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // C
716     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // D
717     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // E
718     O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O,  O, // F
719];