lib.rs 53.9 KB
Newer Older
1
2
3
extern crate byteorder;
use byteorder::ByteOrder;
use byteorder::BigEndian as BE;
Dylan Ede's avatar
Dylan Ede committed
4
use ::std::ops::Deref;
Azriel Hoh's avatar
Azriel Hoh committed
5
#[derive(Clone, Debug)]
Dylan Ede's avatar
Dylan Ede committed
6
7
pub struct FontInfo<Data: Deref<Target=[u8]>> {
    data: Data,       // pointer to .ttf file
8
9
10
11
12
13
14
    // fontstart: usize,       // offset of start of font
    num_glyphs: u32,       // number of glyphs, needed for range checking
    loca: u32,
    head: u32,
    glyf: u32,
    hhea: u32,
    hmtx: u32,
15
    name: u32,
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    kern: u32,            // table locations as offset from start of .ttf
    index_map: u32,       // a cmap mapping for our chosen character encoding
    index_to_loc_format: u32 // format needed to map from glyph index to glyph
}

/*
struct Bitmap<'a>
{
    pub w: i32,
    pub h: i32,
    pub stride: i32,
    pub pixels: &'a mut [u8]
}*/

#[derive(Copy, Clone, Debug)]
#[repr(C)]
pub struct Vertex {
    pub x: i16,
    pub y: i16,
    pub cx: i16,
    pub cy: i16,
37
38
39
40
41
    type_: u8
}

impl Vertex {
    pub fn vertex_type(&self) -> VertexType {
42
43
44
45
46
47
        match self.type_ {
            1 => VertexType::MoveTo,
            2 => VertexType::LineTo,
            3 => VertexType::CurveTo,
            type_ => panic!("Invalid vertex type: {}", type_),
        }
48
    }
49
50
}

51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#[test]
fn test_vertex_type() {
    fn v(type_: VertexType) -> Vertex {
        Vertex { x: 0, y: 0, cx: 0, cy: 0, type_: type_ as u8 }
    }
    assert_eq!(v(VertexType::MoveTo).vertex_type(), VertexType::MoveTo);
    assert_eq!(v(VertexType::LineTo).vertex_type(), VertexType::LineTo);
    assert_eq!(v(VertexType::CurveTo).vertex_type(), VertexType::CurveTo);
}

#[test]
#[should_panic]
fn test_invalid_vertex_type() {
    let v = Vertex { x: 0, y: 0, cx: 0, cy: 0, type_: 255 };
    let s = match v.vertex_type() {
        VertexType::MoveTo => "move to",
        VertexType::LineTo => "line to",
        VertexType::CurveTo => "curve to",
    };
    // With `Vertex::vertex_type` defined as `transmute` this would be undefined behavior:
    println!("{}", s);
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#[repr(u8)]
pub enum VertexType {
    MoveTo = 1,
    LineTo = 2,
    CurveTo = 3
}

#[derive(Copy, Clone, Debug)]
pub struct Rect<T> {
    pub x0: T,
    pub y0: T,
    pub x1: T,
    pub y1: T
}

#[derive(Copy, Clone, Debug)]
pub struct HMetrics {
    pub advance_width: i32,
    pub left_side_bearing: i32
}

#[derive(Copy, Clone, Debug)]
pub struct VMetrics {
    pub ascent: i32,
    pub descent: i32,
    pub line_gap: i32
}

103
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
104
#[repr(C)]
105
pub enum PlatformId { // platformID
106
107
   Unicode   = 0,
   Mac       = 1,
108
   Iso       = 2,
109
110
   Microsoft = 3
}
111
112
fn platform_id(v: u16) -> Option<PlatformId> {
    use PlatformId::*;
113
114
115
    match v {
        0 => Some(Unicode),
        1 => Some(Mac),
116
        2 => Some(Iso),
117
118
119
120
121
        3 => Some(Microsoft),
        _ => None
    }
}

122
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
123
#[repr(C)]
124
#[allow(non_camel_case_types)]
125
pub enum UnicodeEid { // encodingID for PLATFORM_ID_UNICODE
126
127
   Unicode_1_0       = 0,
   Unicode_1_1       = 1,
128
129
   Iso_10646         = 2,
   Unicode_2_0_Bmp   = 3,
130
   Unicode_2_0_Full = 4
131
}
132
133
fn unicode_eid(v: u16) -> Option<UnicodeEid> {
    use UnicodeEid::*;
134
135
136
    match v {
        0 => Some(Unicode_1_0),
        1 => Some(Unicode_1_1),
137
138
        2 => Some(Iso_10646),
        3 => Some(Unicode_2_0_Bmp),
139
140
141
142
        4 => Some(Unicode_2_0_Full),
        _ => None,
    }
}
143

144
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
145
#[repr(C)]
146
pub enum MicrosoftEid { // encodingID for PLATFORM_ID_MICROSOFT
147
148
149
150
151
   Symbol        =0,
   UnicodeBMP    =1,
   Shiftjis      =2,
   UnicodeFull   =10
}
152
153
fn microsoft_eid(v: u16) -> Option<MicrosoftEid> {
    use MicrosoftEid::*;
154
155
156
157
158
159
160
161
162
    match v {
        0 => Some(Symbol),
        1 => Some(UnicodeBMP),
        2 => Some(Shiftjis),
        10 => Some(UnicodeFull),
        _ => None
    }
}

163
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
164
#[repr(C)]
165
pub enum MacEid { // encodingID for PLATFORM_ID_MAC; same as Script Manager codes
166
167
168
169
170
   Roman        =0,   Arabic       =4,
   Japanese     =1,   Hebrew       =5,
   ChineseTrad  =2,   Greek        =6,
   Korean       =3,   Russian      =7
}
171
172
fn mac_eid(v: u16) -> Option<MacEid> {
    use MacEid::*;
173
174
175
176
177
178
179
180
181
182
183
184
    match v {
        0 => Some(Roman),
        1 => Some(Japanese),
        2 => Some(ChineseTrad),
        3 => Some(Korean),
        4 => Some(Arabic),
        5 => Some(Hebrew),
        6 => Some(Greek),
        7 => Some(Russian),
        _ => None
    }
}
185

186
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
187
#[repr(C)]
188
pub enum MicrosoftLang { // languageID for PLATFORM_ID_MICROSOFT; same as LCID...
189
190
191
192
193
194
195
196
       // problematic because there are e.g. 16 english LCIDs and 16 arabic LCIDs
   English     =0x0409,   Italian     =0x0410,
   Chinese     =0x0804,   Japanese    =0x0411,
   Dutch       =0x0413,   Korean      =0x0412,
   French      =0x040c,   Russian     =0x0419,
   German      =0x0407,   //Spanish     =0x0409,
   Hebrew      =0x040d,   Swedish     =0x041D
}
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
fn microsoft_lang(v: u16) -> Option<MicrosoftLang> {
    use MicrosoftLang::*;
    match v {
        0x0409 => Some(English),
        0x0804 => Some(Chinese),
        0x0413 => Some(Dutch),
        0x040c => Some(French),
        0x0407 => Some(German),
        0x040d => Some(Hebrew),
        0x0410 => Some(Italian),
        0x0411 => Some(Japanese),
        0x0412 => Some(Korean),
        0x0419 => Some(Russian),
        0x041D => Some(Swedish),
        _ => None,
    }
}
214

215
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
216
#[repr(C)]
217
pub enum MacLang { // languageID for PLATFORM_ID_MAC
218
219
220
221
222
223
224
225
   English      =0 ,   Japanese     =11,
   Arabic       =12,   Korean       =23,
   Dutch        =4 ,   Russian      =32,
   French       =1 ,   Spanish      =6 ,
   German       =2 ,   Swedish      =5 ,
   Hebrew       =10,   ChineseSimplified =33,
   Italian      =3 ,   ChineseTrad =19
}
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
fn mac_lang(v: u16) -> Option<MacLang> {
    use MacLang::*;
    match v {
        0 => Some(English),
        12 => Some(Arabic),
        4 => Some(Dutch),
        1 => Some(French),
        2 => Some(German),
        10 => Some(Hebrew),
        3 => Some(Italian),
        11 => Some(Japanese),
        23 => Some(Korean),
        32 => Some(Russian),
        6 => Some(Spanish),
        5 => Some(Swedish),
        33 => Some(ChineseSimplified),
        19 => Some(ChineseTrad),
        _ => None,
    }
}
246

247
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
248
249
250
251
252
pub enum PlatformEncodingLanguageId {
    Unicode(Option<Result<UnicodeEid, u16>>, Option<u16>),
    Mac(Option<Result<MacEid, u16>>, Option<Result<MacLang, u16>>),
    Iso(Option<u16>, Option<u16>),
    Microsoft(Option<Result<MicrosoftEid, u16>>, Option<Result<MicrosoftLang, u16>>),
253
}
254
fn platform_encoding_id(platform_id: PlatformId, encoding_id: Option<u16>, language_id: Option<u16>) -> PlatformEncodingLanguageId {
255
    match platform_id {
256
        PlatformId::Unicode => PlatformEncodingLanguageId::Unicode(
257
258
            encoding_id.map(|id| unicode_eid(id).ok_or(id)),
            language_id),
259
        PlatformId::Mac => PlatformEncodingLanguageId::Mac(
260
261
            encoding_id.map(|id| mac_eid(id).ok_or(id)),
            language_id.map(|id| mac_lang(id).ok_or(id))),
262
        PlatformId::Iso => PlatformEncodingLanguageId::Iso(
263
264
            encoding_id,
            language_id),
265
        PlatformId::Microsoft => PlatformEncodingLanguageId::Microsoft(
266
267
            encoding_id.map(|id| microsoft_eid(id).ok_or(id)),
            language_id.map(|id| microsoft_lang(id).ok_or(id))),
268
269
270
    }
}

271
// # accessors to parse data from file
272

273
274
// on platforms that don't allow misaligned reads, if we want to allow
// truetype fonts that aren't padded to alignment, define ALLOW_UNALIGNED_TRUETYPE
275

276
277
278
279
280
/// Return `true` if `data` holds a font stored in a format this crate
/// recognizes, according to its signature in the initial bytes.
pub fn is_font(data: &[u8]) -> bool {
    if data.len() >= 4 {
        let tag = &data[0..4];
281
282
283
284
        tag == [b'1', 0, 0, 0] || tag == b"typ1" || tag == b"OTTO" || tag == [0, 1, 0, 0]
    } else {
        false
    }
285
286
}

287
288
289
290
291
/// Return `true` if `data` holds a TrueType Collection, according to its
/// signature in the initial bytes. A TrueType Collection stores several fonts
/// in a single file, allowing them to share data for glyphs they have in
/// common.
pub fn is_collection(data: &[u8]) -> bool {
Alex Butler's avatar
Alex Butler committed
292
    data.len() >= 4 && &data[0..4] == b"ttcf"
293
294
}

295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
fn find_table(data: &[u8], fontstart: usize, tag: &[u8]) -> u32 {
   let num_tables = BE::read_u16(&data[fontstart+4..]);
   let tabledir = fontstart + 12;
   for i in 0..num_tables {
       let loc = tabledir + 16*(i as usize);
       if &data[loc..loc+4] == tag {
           return BE::read_u32(&data[loc+8..]);
       }
   }
   return 0;
}

/// Each .ttf/.ttc file may have more than one font. Each font has a sequential
/// index number starting from 0. Call this function to get the font offset for
/// a given index; it returns None if the index is out of range. A regular .ttf
/// file will only define one font and it always be at offset 0, so it will
/// return Some(0) for index 0, and None for all other indices. You can just skip
/// this step if you know it's that kind of font.
pub fn get_font_offset_for_index(font_collection: &[u8], index: i32) -> Option<u32> {
   // if it's just a font, there's only one valid index
   if is_font(font_collection) {
      return if index == 0 { Some(0) } else { None };
   }
   // check if it's a TTC
319
   if is_collection(font_collection) {
320
321
322
323
324
325
326
327
328
329
330
331
      // version 1?
      if BE::read_u32(&font_collection[4..]) == 0x00010000 || BE::read_u32(&font_collection[4..]) == 0x00020000 {
         let n = BE::read_i32(&font_collection[8..]);
         if index >= n {
             return None;
         }
         return Some(BE::read_u32(&font_collection[12+(index as usize)*4..]));
      }
   }
   return None;
}

Dylan Ede's avatar
Dylan Ede committed
332
impl<Data: Deref<Target=[u8]>> FontInfo<Data> {
333
334
335

    /// Given an offset into the file that defines a font, this function builds
    /// the necessary cached info for the rest of the system.
Dylan Ede's avatar
Dylan Ede committed
336
    pub fn new(data: Data, fontstart: usize) -> Option<FontInfo<Data>> {
337
338
339
340
341
342
        let cmap = find_table(&data, fontstart, b"cmap"); // required
        let loca = find_table(&data, fontstart, b"loca"); // required
        let head = find_table(&data, fontstart, b"head"); // required
        let glyf = find_table(&data, fontstart, b"glyf"); // required
        let hhea = find_table(&data, fontstart, b"hhea"); // required
        let hmtx = find_table(&data, fontstart, b"hmtx"); // required
343
        let name = find_table(&data, fontstart, b"name"); // not required
344
        let kern = find_table(&data, fontstart, b"kern"); // not required
345
346
347
        if cmap == 0 || loca == 0 || head == 0 || glyf == 0 || hhea == 0 || hmtx == 0 {
            return None;
        }
348
        let t = find_table(&data, fontstart, b"maxp");
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
        let num_glyphs = if t != 0 {
            BE::read_u16(&data[t as usize +4..])
        } else {
            0xffff
        };

        // find a cmap encoding table we understand *now* to avoid searching
        // later. (todo: could make this installable)
        // the same regardless of glyph.
        let num_tables = BE::read_u16(&data[cmap as usize + 2..]);
        let mut index_map = 0;
        for i in 0..num_tables {
            let encoding_record = (cmap + 4 + 8*(i as u32)) as usize;
            // find an encoding we understand:
            match platform_id(BE::read_u16(&data[encoding_record..])) {
364
                Some(PlatformId::Microsoft) => {
365
                    match microsoft_eid(BE::read_u16(&data[encoding_record+2..])) {
366
                        Some(MicrosoftEid::UnicodeBMP) | Some(MicrosoftEid::UnicodeFull) => {
367
368
369
370
371
372
                            // MS/Unicode
                            index_map = cmap + BE::read_u32(&data[encoding_record + 4..]);
                        }
                        _ => ()
                    }
                }
373
                Some(PlatformId::Unicode) => {
374
375
376
377
378
379
380
381
382
383
                    // Mac/iOS has these
                    // all the encodingIDs are unicode, so we don't bother to check it
                    index_map = cmap + BE::read_u32(&data[encoding_record + 4..]);
                },
                _ => ()
            }
        }
        if index_map == 0 {
            return None
        }
384
        let index_to_loc_format = BE::read_u16(&data[head as usize + 50..]) as u32;
385
386
387
388
389
390
391
392
        Some(FontInfo {
            // fontstart: fontstart,
            data: data,
            loca: loca,
            head: head,
            glyf: glyf,
            hhea: hhea,
            hmtx: hmtx,
393
            name: name,
394
395
396
            kern: kern,
            num_glyphs: num_glyphs as u32,
            index_map: index_map,
397
            index_to_loc_format: index_to_loc_format
398
399
400
        })
    }

401
402
403
404
    pub fn get_num_glyphs(&self) -> u32 {
        self.num_glyphs
    }

405
406
407
408
409
    /// If you're going to perform multiple operations on the same character
    /// and you want a speed-up, call this function with the character you're
    /// going to process, then use glyph-based functions instead of the
    /// codepoint-based functions.
    pub fn find_glyph_index(&self, unicode_codepoint: u32) -> u32 {
410
        let data = &self.data;
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
        let index_map = &data[self.index_map as usize..];//self.index_map as usize;

        let format = BE::read_u16(index_map);
        match format {
            0 => { // apple byte encoding
                let bytes = BE::read_u16(&index_map[2..]);
                if unicode_codepoint < bytes as u32 - 6 {
                    return index_map[6 + unicode_codepoint as usize] as u32;
                }
                return 0;
            }
            6 => {
                let first = BE::read_u16(&index_map[6..]) as u32;
                let count = BE::read_u16(&index_map[8..]) as u32;
                if unicode_codepoint >= first && unicode_codepoint < first + count {
                    return BE::read_u16(&index_map[10 + (unicode_codepoint - first) as usize * 2..]) as u32;
                }
                return 0;
            }
            2 => { // @TODO: high-byte mapping for japanese/chinese/korean
                panic!("Index map format unsupported: 2");
            }
            4 => { // standard mapping for windows fonts: binary search collection of ranges
                let segcount = BE::read_u16(&index_map[6..]) as usize >> 1;
                let mut search_range = BE::read_u16(&index_map[8..]) as usize >> 1;
                let mut entry_selector = BE::read_u16(&index_map[10..]);
                let range_shift = BE::read_u16(&index_map[12..]) as usize >> 1;

                // do a binary search of the segments
                let end_count = self.index_map as usize + 14;
                let mut search = end_count;

                if unicode_codepoint > 0xffff {
                    return 0;
                }

                // they lie from endCount .. endCount + segCount
                // but searchRange is the nearest power of two, so...
                if unicode_codepoint >= BE::read_u16(&data[search + range_shift*2..]) as u32 {
                    search += range_shift*2;
                }

                // now decrement to bias correctly to find smallest
                search -= 2;
                while entry_selector != 0 {
                    search_range >>= 1;
                    let end = BE::read_u16(&data[search + search_range*2..]) as u32;
                    if unicode_codepoint > end {
                        search += search_range * 2;
                    }
                    entry_selector -= 1;
                }
                search += 2;

                {
                    let item = (search - end_count) >> 1;
                    assert!(unicode_codepoint <= BE::read_u16(&data[end_count + 2*item..]) as u32);
                    let start = BE::read_u16(&index_map[14 + segcount*2 + 2 + 2*item..]) as u32;
                    if unicode_codepoint < start {
                        return 0;
                    }
                    let offset = BE::read_u16(&index_map[14 + segcount*6 + 2 + 2*item..]) as usize;
                    if offset == 0 {
                        return (unicode_codepoint as i32 + BE::read_i16(
                            &index_map[14 + segcount*4 + 2 + 2*item..]) as i32) as u16 as u32;
                    }
                    return BE::read_u16(&index_map[
                        offset + (unicode_codepoint-start) as usize * 2
                            + 14 + segcount*6 + 2 + 2*item..]) as u32;
                }
            }
            12 | 13 => {
                let ngroups = BE::read_u32(&index_map[12..]) as usize;
                let mut low = 0;
                let mut high = ngroups;
                // Binary search of the right group
                while low < high {
                    let mid = low + ((high - low) >> 1); // rounds down, so low <= mid < high
                    let start_char = BE::read_u32(&index_map[16 + mid*12..]);
                    let end_char = BE::read_u32(&index_map[16 + mid*12 + 4..]);
                    if unicode_codepoint < start_char {
                        high = mid;
                    } else if unicode_codepoint > end_char {
                        low = mid + 1;
                    } else {
                        let start_glyph = BE::read_u32(&index_map[16 + mid*12 + 8..]);
                        if format == 12 {
                            return start_glyph + unicode_codepoint - start_char;
                        } else {
                            return start_glyph;
                        }
                    }
                }
Dylan Ede's avatar
Dylan Ede committed
504
                return 0;
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
            }
            n => panic!("Index map format unsupported: {}", n)
        }
    }

    /// Returns the series of vertices encoding the shape of the glyph for this codepoint.
    ///
    /// The shape is a series of countours. Each one starts with
    /// a moveto, then consists of a series of mixed
    /// lineto and curveto segments. A lineto
    /// draws a line from previous endpoint to its x,y; a curveto
    /// draws a quadratic bezier from previous endpoint to
    /// its x,y, using cx,cy as the bezier control point.
    pub fn get_codepoint_shape(&self, unicode_codepoint: u32) -> Option<Vec<Vertex>> {
        self.get_glyph_shape(self.find_glyph_index(unicode_codepoint))
    }

    fn get_glyf_offset(&self, glyph_index: u32) -> Option<u32> {
        let g1;
        let g2;
        if glyph_index >= self.num_glyphs || self.index_to_loc_format >= 2 {
            // glyph index out of range or unknown index->glyph map format
            return None;
        }

        if self.index_to_loc_format == 0 {
            g1 = self.glyf + BE::read_u16(&self.data[(self.loca + glyph_index*2) as usize..]) as u32 * 2;
            g2 = self.glyf + BE::read_u16(&self.data[(self.loca + glyph_index*2 + 2) as usize..]) as u32 * 2;
        } else {
            g1 = self.glyf + BE::read_u32(&self.data[(self.loca + glyph_index * 4) as usize..]);
            g2 = self.glyf + BE::read_u32(&self.data[(self.loca + glyph_index * 4 + 4) as usize..]);
        }
        if g1 == g2 {
            None
        } else {
            Some(g1)
        }
    }

    /// Like `get_codepoint_box`, but takes a glyph index. Use this if you have cached the glyph index for
    /// a codepoint.
    pub fn get_glyph_box(&self, glyph_index: u32) -> Option<Rect<i16>> {
        let g = match self.get_glyf_offset(glyph_index) {
            Some(v) => v as usize,
            None => return None
        };
        Some(Rect {
            x0: BE::read_i16(&self.data[g + 2..]),
            y0: BE::read_i16(&self.data[g + 4..]),
            x1: BE::read_i16(&self.data[g + 6..]),
            y1: BE::read_i16(&self.data[g + 8..])
        })
    }

    /// Gets the bounding box of the visible part of the glyph, in unscaled coordinates
    pub fn get_codepoint_box(&self, codepoint: u32) -> Option<Rect<i16>> {
        self.get_glyph_box(self.find_glyph_index(codepoint))
    }

    /// returns true if nothing is drawn for this glyph
    pub fn is_glyph_empty(&self, glyph_index: u32) -> bool {
        match self.get_glyf_offset(glyph_index) {
            Some(g) => {
                let number_of_contours = BE::read_i16(&self.data[g as usize..]);
                number_of_contours == 0
            },
            None => true
        }
    }
    /// Like `get_codepoint_shape`, but takes a glyph index instead. Use this if you have cached the
    /// glyph index for a codepoint.
    pub fn get_glyph_shape(&self, glyph_index: u32) -> Option<Vec<Vertex>> {
        use VertexType::*;
        fn close_shape(vertices: &mut [Vertex], num_vertices: &mut usize, was_off: bool, start_off: bool,
                       sx: i32, sy: i32, scx: i32, scy: i32, cx: i32, cy: i32) {
            use VertexType::*;
            if start_off {
                if was_off {
                    vertices[*num_vertices] = Vertex {
584
                        type_: CurveTo as u8,
585
586
587
588
589
590
591
592
                        x: ((cx+scx)>>1) as i16,
                        y: ((cy+scy)>>1) as i16,
                        cx: cx as i16,
                        cy: cy as i16
                    };
                    *num_vertices += 1;
                }
                vertices[*num_vertices] = Vertex {
593
                    type_: CurveTo as u8,
594
595
596
597
598
599
600
601
                    x: sx as i16,
                    y: sy as i16,
                    cx: scx as i16,
                    cy: scy as i16
                };
            } else {
                vertices[*num_vertices] = if was_off {
                    Vertex {
602
                        type_: CurveTo as u8,
603
604
605
606
607
608
609
                        x: sx as i16,
                        y: sy as i16,
                        cx: cx as i16,
                        cy: cy as i16
                    }
                } else {
                    Vertex {
610
                        type_: LineTo as u8,
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
                        x: sx as i16,
                        y: sy as i16,
                        cx: 0,
                        cy: 0
                    }
                };
            }
            *num_vertices += 1;
        }

        let g = match self.get_glyf_offset(glyph_index){
            Some(g) => &self.data[g as usize..],
            None => return None
        };

        let number_of_contours = BE::read_i16(g);
        let vertices: Vec<Vertex> = if number_of_contours > 0 {
            let number_of_contours = number_of_contours as usize;
            let mut start_off = false;
            let mut was_off = false;
            let end_points_of_contours = &g[10..];
            let ins = BE::read_u16(&g[10 + number_of_contours * 2..]) as usize;
            let mut points = &g[10 + number_of_contours * 2 + 2 + ins..];

            let n = 1 + BE::read_u16(&end_points_of_contours[number_of_contours*2 - 2..]) as usize;

            let m = n + 2 * number_of_contours; // a loose bound on how many vertices we might need
            let mut vertices: Vec<Vertex> = Vec::with_capacity(m);
            unsafe{ vertices.set_len(m) };

            let mut next_move = 0;
            let mut flagcount = 0;

            // in first pass, we load uninterpreted data into the allocated array
            // above, shifted to the end of the array so we won't overwrite it when
            // we create our final data starting from the front

            // starting offset for uninterpreted data, regardless of how m ends up being calculated
            let off = m - n;

            // first load flags
            let mut flags = 0;
            for i in 0..n {
                if flagcount == 0 {
                    flags = points[0];
                    points = &points[1..];
                    if flags & 8 != 0 {
                        flagcount = points[0];
                        points = &points[1..];
                    }
                } else {
                    flagcount -= 1;
                }
664
                vertices[off + i].type_ = flags;
665
666
667
668
669
            }

            // now load x coordinates
            let mut x = 0i32;
            for i in 0..n {
670
671
672
673
                let flags = vertices[off + i].type_;
                if flags == 255 {
                    println!("{:?}", flags);
                }
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
                if flags & 2 != 0 {
                    let dx = points[0] as i32;
                    points = &points[1..];
                    if flags & 16 != 0 { // ???
                        x += dx;
                    } else {
                        x -= dx;
                    }
                } else {
                    if flags & 16 == 0 {
                        x += points[0] as i32 * 256 + points[1] as i32;
                        points = &points[2..];
                    }
                }
                vertices[off + i].x = x as i16;
            }

            // now load y coordinates
            let mut y = 0i32;
            for i in 0..n {
694
                let flags = vertices[off + i].type_;
695
696
697
698
699
700
701
702
703
704
                if flags & 4 != 0 {
                    let dy = points[0] as i32;
                    points = &points[1..];
                    if flags & 32 != 0 {
                        y += dy;
                    } else {
                        y -= dy;
                    }
                } else {
                    if flags & 32 == 0 {
705
                        y += points[0] as i32 * 256 + points[1] as i32;
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
                        points = &points[2..];
                    }
                }
                vertices[off + i].y = y as i16;
            }

            // now convert them to our format
            let mut num_vertices = 0;
            let mut sx = 0;
            let mut sy = 0;
            let mut cx = 0;
            let mut cy = 0;
            let mut scx = 0;
            let mut scy = 0;
            let mut i = 0;
            let mut j = 0;
            while i < n {
723
                let flags = vertices[off + i].type_;
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
                x = vertices[off + i].x as i32;
                y = vertices[off + i].y as i32;

                if next_move == i {
                    if i != 0 {
                        close_shape(&mut vertices[..], &mut num_vertices, was_off, start_off, sx, sy, scx, scy, cx, cy);
                    }

                    // now start the new one
                    start_off = flags & 1 == 0;
                    if start_off {
                        // if we start off with an off-curve point, then when we need to find a point on the curve
                        // where we can start, and we need to save some state for when we wraparound.
                        scx = x;
                        scy = y;
                        if vertices[off+i+1].type_ as u8 & 1 == 0 {
                            // next point is also a curve point, so interpolate an on-point curve
                            sx = (x + vertices[off + i + 1].x as i32) >> 1;
                            sy = (y + vertices[off + i + 1].y as i32) >> 1;
                        } else {
                            // otherwise just use the next point as our start point
                            sx = vertices[off + i + 1].x as i32;
                            sy = vertices[off + i + 1].y as i32;
                            i += 1; // we're using point i+1 as the starting point, so skip it
                        }
                    } else {
                        sx = x;
                        sy = y;
                    }
                    vertices[num_vertices] = Vertex {
754
                        type_: MoveTo as u8,
755
756
757
758
759
760
761
762
763
764
765
766
767
768
                        x: sx as i16,
                        y: sy as i16,
                        cx: 0,
                        cy: 0
                    };
                    num_vertices += 1;
                    was_off = false;
                    next_move = 1 + BE::read_u16(&end_points_of_contours[j*2..]) as usize;
                    j += 1;
                } else {
                    if flags & 1 == 0 { // if it's a curve
                        if was_off {
                            // two off-curve control points in a row means interpolate an on-curve midpoint
                            vertices[num_vertices] = Vertex {
769
                                type_: CurveTo as u8,
770
771
772
773
774
775
776
777
778
779
780
781
782
                                x: ((cx+x) >> 1) as i16,
                                y: ((cy+y) >> 1) as i16,
                                cx: cx as i16,
                                cy: cy as i16
                            };
                            num_vertices += 1;
                        }
                        cx = x;
                        cy = y;
                        was_off = true;
                    } else {
                        if was_off {
                            vertices[num_vertices] = Vertex {
783
                                type_: CurveTo as u8,
784
785
786
787
788
789
790
                                x: x as i16,
                                y: y as i16,
                                cx: cx as i16,
                                cy: cy as i16
                            }
                        } else {
                            vertices[num_vertices] = Vertex {
791
                                type_: LineTo as u8,
792
793
794
795
796
797
798
799
800
801
802
803
804
805
                                x: x as i16,
                                y: y as i16,
                                cx: 0 as i16,
                                cy: 0 as i16
                            }
                        }
                        num_vertices += 1;
                        was_off = false;
                    }
                }
                i += 1;
            }
            close_shape(&mut vertices[..], &mut num_vertices, was_off, start_off, sx, sy, scx, scy, cx, cy);
            assert!(num_vertices <= vertices.len());
Alex Butler's avatar
Alex Butler committed
806
            vertices.truncate(num_vertices);
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
            vertices
        } else if number_of_contours == -1 {
            // Compound shapes
            let mut more = true;
            let mut comp = &g[10..];
            let mut vertices = Vec::new();
            while more {
                let mut mtx = [1.0, 0.0,
                               0.0, 1.0,
                               0.0, 0.0];

                let flags = BE::read_i16(comp);
                comp = &comp[2..];
                let gidx = BE::read_u16(comp);
                comp = &comp[2..];

                if flags & 2 != 0 { // XY values
                    if flags & 1 != 0 { // shorts
                        mtx[4] = BE::read_i16(comp) as f32;
                        comp = &comp[2..];
                        mtx[5] = BE::read_i16(comp) as f32;
                        comp = &comp[2..];
                    } else {
                        mtx[4] = comp[0] as f32;
                        comp = &comp[1..];
                        mtx[5] = comp[0] as f32;
                        comp = &comp[1..];
                    }
                } else {
                    panic!("Matching points not supported.");
                }
                if flags & (1<<3) != 0 { // WE_HAVE_A_SCALE
                    mtx[0] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                    mtx[1] = 0.0;
                    mtx[2] = 0.0;
                    mtx[3] = mtx[0];
                } else if flags & (1<<6) != 0 { // WE_HAVE_AN_X_AND_YSCALE
                    mtx[0] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                    mtx[1] = 0.0;
                    mtx[2] = 0.0;
                    mtx[3] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                } else if flags & (1<<7) != 0 { // WE_HAVE_A_TWO_BY_TWO
                    mtx[0] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                    mtx[1] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                    mtx[2] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                    mtx[3] = BE::read_i16(comp) as f32 / 16384.0;
                    comp = &comp[2..];
                }

                // Find transformation scales.
                let m = (mtx[0]*mtx[0] + mtx[1]*mtx[1]).sqrt();
                let n = (mtx[2]*mtx[2] + mtx[3]*mtx[3]).sqrt();

                // Get indexed glyph.
                let mut comp_verts = self.get_glyph_shape(gidx as u32).unwrap_or_else(|| Vec::new());
                if comp_verts.len() > 0 {
                    // Transform vertices
                    for v in &mut *comp_verts {
                        let (x, y, cx, cy) = (v.x as f32, v.y as f32, v.cx as f32, v.cy as f32);
                        *v = Vertex {
                            type_: v.type_,
                            x: (m * (mtx[0]*x + mtx[2]*y + mtx[4])) as i16,
                            y: (n * (mtx[1]*x + mtx[3]*y + mtx[5])) as i16,
                            cx: (m * (mtx[0]*cx + mtx[2]*cy + mtx[4])) as i16,
                            cy: (n * (mtx[1]*cx + mtx[3]*cy + mtx[5])) as i16
                        };
                    }
                    // Append vertices.
                    vertices.append(&mut comp_verts);
                }
                // More components ?
                more = flags & (1<<5) != 0;
            }
            vertices
        } else if number_of_contours < 0 {
            panic!("Contour format not supported.")
        } else {
            return None
        };
        Some(vertices)
    }

    /// like `get_codepoint_h_metrics`, but takes a glyph index instead. Use this if you have cached the
    /// glyph index for a codepoint.
    pub fn get_glyph_h_metrics(&self, glyph_index: u32) -> HMetrics {
        let num_of_long_hor_metrics = BE::read_u16(&self.data[self.hhea as usize + 34..]) as usize;
        if (glyph_index as usize) < num_of_long_hor_metrics {
            HMetrics {
                advance_width:
                BE::read_i16(&self.data[self.hmtx as usize + 4*glyph_index as usize..]) as i32,
                left_side_bearing:
                BE::read_i16(&self.data[self.hmtx as usize + 4*glyph_index as usize + 2..]) as i32,
            }
        } else {
            HMetrics {
                advance_width:
                BE::read_i16(&self.data[self.hmtx as usize + 4*(num_of_long_hor_metrics-1)..]) as i32,
                left_side_bearing:
                BE::read_i16(&self.data[self.hmtx as usize + 4*num_of_long_hor_metrics + 2*(glyph_index as isize - num_of_long_hor_metrics as isize) as usize..]) as i32
            }
        }
    }

    /// like `get_codepoint_kern_advance`, but takes glyph indices instead. Use this if you have cached the
    /// glyph indices for the codepoints.
    pub fn get_glyph_kern_advance(&self, glyph_1: u32, glyph_2: u32) -> i32 {
        let kern = &self.data[self.kern as usize..];
        // we only look at the first table. it must be 'horizontal' and format 0
        if self.kern == 0 || BE::read_u16(&kern[2..]) < 1 || BE::read_u16(&kern[8..]) != 1 {
            // kern not present, OR
            // no tables (need at least one), OR
            // horizontal flag not set in format
            return 0;
        }

Dylan Ede's avatar
Dylan Ede committed
928
        let mut l: i32 = 0;
929
        let mut r: i32 = BE::read_u16(&kern[10..]) as i32 - 1;
930
931
932
933
934
        let needle = glyph_1 << 16 | glyph_2;
        while l <= r {
            let m = (l + r) >> 1;
            let straw = BE::read_u32(&kern[18+(m as usize)*6..]); // note: unaligned read
            if needle < straw {
Dylan Ede's avatar
Dylan Ede committed
935
                r = m - 1;
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
            } else if needle > straw {
                l = m + 1;
            } else {
                return BE::read_i16(&kern[22+(m as usize)*6..]) as i32;
            }
        }
        0
    }

    /// an additional amount to add to the 'advance' value between cp1 and cp2
    pub fn get_codepoint_kern_advance(&self, cp1: u32, cp2: u32) -> i32 {
        if self.kern == 0 { // if no kerning table, don't waste time looking up both codepoint->glyphs
            0
        } else {
            self.get_glyph_kern_advance(self.find_glyph_index(cp1), self.find_glyph_index(cp2))
        }
    }

    /// `left_side_bearing` is the offset from the current horizontal position to the left edge of the character
    /// `advance_width` is the offset from the current horizontal position to the next horizontal position
    /// these are expressed in unscaled coordinates
    pub fn get_codepoint_h_metrics(&self, codepoint: u32) -> HMetrics {
        self.get_glyph_h_metrics(self.find_glyph_index(codepoint))
    }

    /// `ascent` is the coordinate above the baseline the font extends; descent
    /// is the coordinate below the baseline the font extends (i.e. it is typically negative)
    /// `line_gap` is the spacing between one row's descent and the next row's ascent...
    /// so you should advance the vertical position by `ascent - descent + line_gap`
    /// these are expressed in unscaled coordinates, so you must multiply by
    /// the scale factor for a given size
    pub fn get_v_metrics(&self) -> VMetrics {
        let hhea = &self.data[self.hhea as usize..];
        VMetrics {
            ascent: BE::read_i16(&hhea[4..]) as i32,
            descent: BE::read_i16(&hhea[6..]) as i32,
            line_gap: BE::read_i16(&hhea[8..]) as i32
        }
    }

    /// the bounding box around all possible characters
    pub fn get_bounding_box(&self) -> Rect<i16> {
        let head = &self.data[self.head as usize..];
        Rect {
            x0: BE::read_i16(&head[36..]),
            y0: BE::read_i16(&head[38..]),
            x1: BE::read_i16(&head[40..]),
            y1: BE::read_i16(&head[42..])
        }
    }

    /// computes a scale factor to produce a font whose "height" is 'pixels' tall.
    /// Height is measured as the distance from the highest ascender to the lowest
    /// descender; in other words, it's equivalent to calling GetFontVMetrics
    /// and computing:
    ///       scale = pixels / (ascent - descent)
    /// so if you prefer to measure height by the ascent only, use a similar calculation.
    pub fn scale_for_pixel_height(&self, height: f32) -> f32 {
        let hhea = &self.data[self.hhea as usize..];
        let fheight = BE::read_i16(&hhea[4..]) as f32 - BE::read_i16(&hhea[6..]) as f32;
        height / fheight
    }

fschutt's avatar
fschutt committed
999
1000
1001
1002
1003
    /// Returns the units per EM square of this font.
    pub fn units_per_em(&self) -> u16 {
        BE::read_u16(&self.data[self.head as usize + 18..])
    }

1004
1005
1006
1007
    /// computes a scale factor to produce a font whose EM size is mapped to
    /// `pixels` tall. This is probably what traditional APIs compute, but
    /// I'm not positive.
    pub fn scale_for_mapping_em_to_pixels(&self, pixels: f32) -> f32 {
fschutt's avatar
fschutt committed
1008
        pixels / (self.units_per_em() as f32)
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
    }

    /// like `get_codepoint_bitmap_box_subpixel`, but takes a glyph index instead of a codepoint.
    pub fn get_glyph_bitmap_box_subpixel(&self,
                                         glyph: u32,
                                         scale_x: f32, scale_y: f32,
                                         shift_x: f32, shift_y: f32) -> Option<Rect<i32>> {
        if let Some(glyph_box) = self.get_glyph_box(glyph) {
            // move to integral bboxes (treating pixels as little squares, what pixels get touched?)
            Some(Rect {
                x0: (glyph_box.x0 as f32 * scale_x + shift_x).floor() as i32,
                y0: (-glyph_box.y1 as f32 * scale_y + shift_y).floor() as i32,
                x1: (glyph_box.x1 as f32 * scale_x + shift_x).ceil() as i32,
                y1: (-glyph_box.y0 as f32 * scale_y + shift_y).ceil() as i32
            })
        } else { // e.g. space character
            None
        }
    }

    /// like `get_codepoint_bitmap_box`, but takes a glyph index instead of a codepoint.
    pub fn get_glyph_bitmap_box(&self, glyph: u32, scale_x: f32, scale_y: f32) -> Option<Rect<i32>> {
        self.get_glyph_bitmap_box_subpixel(glyph, scale_x, scale_y, 0.0, 0.0)
    }

    /// same as get_codepoint_bitmap_box, but you can specify a subpixel
    /// shift for the character
    pub fn get_codepoint_bitmap_box_subpixel(&self,
                                             codepoint: u32,
                                             scale_x: f32, scale_y: f32,
                                             shift_x: f32, shift_y: f32) -> Option<Rect<i32>> {
        self.get_glyph_bitmap_box_subpixel(self.find_glyph_index(codepoint),
                                           scale_x, scale_y,
                                           shift_x, shift_y)
    }

    /// get the bounding box of the bitmap centered around the glyph origin; so the
    /// bitmap width is x1-x0, height is y1-y0, and location to place
    /// the bitmap top left is (left_side_bearing*scale, y0).
    /// (Note that the bitmap uses y-increases-down, but the shape uses
    /// y-increases-up, so CodepointBitmapBox and CodepointBox are inverted.)
    pub fn get_codepoint_bitmap_box(&self, codepoint: u32, scale_x: f32, scale_y: f32) -> Option<Rect<i32>> {
        self.get_codepoint_bitmap_box_subpixel(codepoint, scale_x, scale_y, 0.0, 0.0)
    }

1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
    pub fn get_font_name_strings(&self) -> FontNameIter<Data> {
        let nm = self.name as usize;
        if nm == 0 {
            return FontNameIter {
                font_info: &self,
                string_offset: 0,
                index: 0,
                count: 0,
            };
        }
        let count = BE::read_u16(&self.data[nm + 2..]) as usize;
        let string_offset = nm + BE::read_u16(&self.data[nm + 4..]) as usize;

        FontNameIter {
            font_info: &self,
            string_offset: string_offset,
            index: 0,
            count: count,
        }
    }

1075
}
1076

1077
#[derive(Clone, Copy)]
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
pub struct FontNameIter<'a, Data: 'a + Deref<Target=[u8]>> {
    /// Font info.
    font_info: &'a FontInfo<Data>,
    string_offset: usize,
    /// Next index.
    index: usize,
    /// Number of name strings.
    count: usize,
}

impl<'a, Data: 'a + Deref<Target=[u8]>> Iterator for FontNameIter<'a, Data> {
1089
    type Item = (&'a [u8], Option<PlatformEncodingLanguageId>, u16);
1090
1091
1092
1093
1094
1095
1096
1097

    fn next(&mut self) -> Option<Self::Item> {
        if self.index >= self.count {
            return None;
        }

        let loc = self.font_info.name as usize + 6 + 12 * self.index;

1098
1099
        let pl_id = platform_id(BE::read_u16(&self.font_info.data[loc + 0..]));
        let platform_encoding_language_id = pl_id.map(|pl_id| {
1100
                let encoding_id = BE::read_u16(&self.font_info.data[loc + 2..]);
1101
1102
                let language_id = BE::read_u16(&self.font_info.data[loc + 4..]);
                platform_encoding_id(pl_id, Some(encoding_id), Some(language_id))
1103
            });
1104
1105
        // @TODO: Define an enum type for Name ID.
        //        See https://www.microsoft.com/typography/otspec/name.htm, "Name IDs" section.
1106
1107
1108
1109
1110
1111
        let name_id = BE::read_u16(&self.font_info.data[loc + 6..]);
        let length = BE::read_u16(&self.font_info.data[loc + 8..]) as usize;
        let offset = self.string_offset + BE::read_u16(&self.font_info.data[loc + 10..]) as usize;

        self.index += 1;

1112
        Some((&self.font_info.data[offset..offset+length], platform_encoding_language_id, name_id))
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.count - self.index;
        (remaining, Some(remaining))
    }

    fn count(self) -> usize {
        self.count - self.index
    }

    fn last(mut self) -> Option<Self::Item> {
        if self.index >= self.count || self.count == 0 {
            return None;
        }
        self.index = self.count - 1;
        self.next()
    }

    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        if n > self.count - self.index {
            self.index = self.count;
            return None;
        }
        self.index += n;
        self.next()
    }
}

1142
// The following code is an unfinished port of the rasteriser in stb_truetype.h
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
/*
struct Edge {
    x0: f32,
    y0: f32,
    x1: f32,
    y1: f32,
    invert: bool
}

struct ActiveEdge {
    next: Option<Box<ActiveEdge>>,
    fx: f32,
    fdx: f32,
    fdy: f32,
    direction: Cell<f32>,
    sy: f32,
    ey: f32
}

fn new_active(e: &Edge, off_x: i32, start_point: f32) -> Box<ActiveEdge> {
    let dxdy = (e.x1 - e.x0) / (e.y1 - e.y0);
    Box::new(ActiveEdge {
        fdx: dxdy,
        fdy: if dxdy != 0.0 {
            1.0 / dxdy
        } else {
            0.0
        },
        fx: (e.x0 + dxdy*(start_point - e.y0)) - off_x as f32,
        direction: Cell::new(if e.invert {
            1.0
        } else {
            -1.0
        }),
        sy: e.y0,
        ey: e.y1,
        next: None
    })
}

// the edge passed in here does not cross the vertical line at x or the vertical line at x+1
// (i.e. it has already been clipped to those)
fn handle_clipped_edge(scanline: &mut [f32], x: i32, e: &ActiveEdge,
                       mut x0: f32, mut y0: f32, mut x1: f32, mut y1: f32) {
    let x_ = x as f32;
    if y0 == y1 {
        return
    }
    assert!(y0 < y1);
    assert!(e.sy <= e.ey);
    if y0 > e.ey || y1 < e.sy {
        return
    }
    if y0 < e.sy {
        x0 += (x1-x0) * (e.ey - y0) / (y1-y0);
        y0 = e.sy;
    }
    if y1 > e.ey {
        x1 += (x1-x0) * (e.ey - y1) / (y1-y0);
        y1 = e.ey;
    }

    if x0 == x_ {
        assert!(x1 <= x_+1.0);
    } else if x0 == x_+1.0 {
        assert!(x1 >= x_);
    } else if x0 <= x_ {
        assert!(x1 <= x_)
    } else if x0 >= x_+1.0 {
        assert!(x1 >= x_+1.0)
    } else {
        assert!(x1 >= x_ && x1 <= x_+1.0)
    }

    if x0 <= x_ && x1 <= x_ {
        scanline[x as usize] += e.direction.get() * (y1-y0);
    } else if x0 >= x_+1.0 && x1 >= x_+1.0 {

    } else {
        assert!(x0 >= x_ && x0 <= x_+1.0 && x1 >= x_ && x1 <= x_+1.0);
        // coverage = 1 - average x position
        scanline[x as usize] += e.direction.get() * (y1-y0) * (1.0-((x0-x_)+(x1-x_))/2.0);
    }
}

fn fill_active_edges_new(scanline: &mut [f32], scanline_fill: &mut [f32], len: i32,
                         mut e_: Option<Box<ActiveEdge>>, y_top: f32) {
    use std::mem::swap;
    let len_ = len as f32;
    let y_bottom = y_top + 1.0;

    while e_.is_some() {
        let e = e_.take().unwrap();
        // brute force every pixel

        // compute intersection points with top & bottom
        assert!(e.ey >= y_top);

        if e.fdx == 0.0 {
            let x0 = e.fx;
            if x0 < len_ {
                if x0 >= 0.0 {
                    handle_clipped_edge(scanline, x0 as i32, &e, x0, y_top, x0, y_bottom);
                    handle_clipped_edge(panic!(), (x0 + 1.0) as i32, &e, x0, y_top, x0, y_bottom);
                } else {
                    handle_clipped_edge(panic!(), 0, &e, x0, y_top, x0, y_bottom);
                }
            }
        } else {
            let mut x0 = e.fx;
            let mut dx = e.fdx;
            let mut xb = x0 + dx;
            let mut x_top;
            let mut x_bottom;
            let mut sy0;
            let mut sy1;
            let mut dy = e.fdy;
            assert!(e.sy <= y_bottom && e.ey >= y_top);

            // compute endpoints of line segment clipped to this scanline (if the
            // line segment starts on this scanline. x0 is the intersection of the
            // line with y_top, but that may be off the line segment.
            if e.sy > y_top {
                x_top = x0 + dx * (e.sy - y_top);
                sy0 = e.sy;
            } else {
                x_top = x0;
                sy0 = y_top;
            }
            if e.ey < y_bottom {
                x_bottom = x0 + dx * (e.ey - y_top);
                sy1 = e.ey;
            } else {
                x_bottom = xb;
                sy1 = y_bottom;
            }

            if x_top >= 0.0 && x_bottom >= 0.0 && x_top < len_ && x_bottom < len_ {
                // from here on, we don't have to range check x values

                if (x_top as i32) == (x_bottom as i32) {
                    let x = x_top as i32;
                    // simple case, only spans one pixel
                    let height = sy1 - sy0;
                    assert!(x >= 0 && x < len);
                    scanline[x as usize] += e.direction.get() * (1.0-((x_top - x as f32) + (x_bottom-x as f32))/2.0) * height;
                    scanline_fill[x as usize] += e.direction.get() * height; // everything right of this pixel is filled
                } else {
                    // covers 2+ pixels
                    if x_top > x_bottom {
                        // flip scanline vertically; signed area is the same
                        sy0 = y_bottom - (sy0 - y_top);
                        sy1 = y_bottom - (sy1 - y_top);
                        swap(&mut sy0, &mut sy1);
                        swap(&mut x_bottom, &mut x_top);
                        dx = -dx;
                        dy = -dy;
                        swap(&mut x0, &mut xb);
                    }

                    let x1 = x_top as i32;
                    let x2 = x_bottom as i32;
                    // compute intersection with y axis at x1+1
                    let mut y_crossing = ((x1+1) as f32 - x0) * dy + y_top;

                    let sign = e.direction.get();
                    // area of the rectangle covered from y0..y_crossing
                    let mut area = sign * (y_crossing-sy0);
                    // area of the triangle (x_top, y0), (x+1, y0), (x+1, y_crossing)
                    scanline[x1 as usize] += area * (1.0-((x_top-x1 as f32)+(x1+1-x1) as f32)/2.0);

                    let step = sign * dy;
                    for x in x1+1..x2 {
                        scanline[x as usize] += area + step/2.0;
                        area += step;
                    }
                    y_crossing += dy * (x2 - (x1+1)) as f32;

                    assert!(area.abs() <= 1.01);

                    scanline[x2 as usize] += area + sign * (1.0-((x2-x2) as f32 +(x_bottom-x2 as f32))/2.0) * (sy1-y_crossing);

                    scanline_fill[x2 as usize] += sign * (sy1-sy0);
                }
            } else {
                // if edge goes outside of box we're drawing, we require
                // clipping logic. since this does not match the intended use
                // of this library, we use a different, very slow brute
                // force implementation
                for x in 0..len {
                    // cases:
                    //
                    // there can be up to two intersections with the pixel. any intersection
                    // with left or right edges can be handled by splitting into two (or three)
                    // regions. intersections with top & bottom do not necessitate case-wise logic.
                    //
                    // the old way of doing this found the intersections with the left & right edges,
                    // then used some simple logic to produce up to three segments in sorted order
                    // from top-to-bottom. however, this had a problem: if an x edge was epsilon
                    // across the x border, then the corresponding y position might not be distinct
                    // from the other y segment, and it might ignored as an empty segment. to avoid
                    // that, we need to explicitly produce segments based on x positions.

                    // rename variables to clear pairs
                    let y0 = y_top;
                    let x1 = x as f32;
                    let x2 = (x+1) as f32;
                    let x3 = xb;
                    let y3 = y_bottom;
                    let y1 = (x as f32 - x0) / dx + y_top;
                    let y2 = (x as f32 + 1.0 - x0) / dx + y_top;

                    if x0 < x1 && x3 > x2 {        // three segments descending down-right
                        handle_clipped_edge(scanline, x, &e, x0, y0, x1, y1);
                        handle_clipped_edge(scanline, x, &e, x1, y1, x2, y2);
                        handle_clipped_edge(scanline, x, &e, x2, y2, x3, y3);
                    } else if x3 < x1 && x0 > x2 { // three segments descending down-left
                        handle_clipped_edge(scanline, x, &e, x0, y0, x2, y2);
                        handle_clipped_edge(scanline, x, &e, x2, y2, x1, y1);
                        handle_clipped_edge(scanline, x, &e, x1, y1, x3, y3);
                    } else if x0 < x1 && x3 > x1 { // two segments across x, down-right
                        handle_clipped_edge(scanline, x, &e, x0, y0, x1, y1);
                        handle_clipped_edge(scanline, x, &e, x1, y1, x3, y3);
                    } else if x3 < x1 && x0 > x1 { // two segments across x, down-left
                        handle_clipped_edge(scanline, x, &e, x0, y0, x1, y1);
                        handle_clipped_edge(scanline, x, &e, x1, y1, x3, y3);
                    } else if x0 < x2 && x3 > x2 { // two segments across x+1, down-right
                        handle_clipped_edge(scanline, x, &e, x0, y0, x2, y2);
                        handle_clipped_edge(scanline, x, &e, x2, y2, x3, y3);
                    } else if x3 < x2 && x0 > x2 { // two segments across x+1, down-left
                        handle_clipped_edge(scanline, x, &e, x0, y0, x2, y2);
                        handle_clipped_edge(scanline, x, &e, x2, y2, x3, y3);
                    } else { // one segment
                        handle_clipped_edge(scanline, x, &e, x0, y0, x3, y3);
                    }
                }
            }
        }
        e_ = e.next;
    }
}

// directly AA rasterize edges w/o supersampling

fn rasterize_sorted_edges(result: &mut Bitmap, e: &mut [Edge], n: i32, vsubsample: i32, off_x: i32, off_y: i32) {
    let scanline = vec![Cell::new(0.0); result.w as usize*2+1];
    let scanline2 = &scanline[result.w as usize..];
    let mut y = off_y as f32;
    e[n as usize].y0 = (off_y + result.h) as f32 + 1.0;

    let mut j = 0;
    let mut active: Option<Box<ActiveEdge>> = None;
    while j < result.h {
        // find center of pixel for this scanline
        let scan_y_top = y + 0.0;
        let scan_y_bottom = y + 1.0;
        let mut step = &mut active;

        for v in &scanline[0..result.w as usize] {
            v.set(0.0)
        }
        for v in &scanline2[0..result.w as usize + 1] {
            v.set(0.0)
        }

        // update all active edges;
        // remove all active edges that terminate before the top of this scanline
        while step.is_some() {
            let z = step.as_ref().unwrap();
            if z.ey <= scan_y_top {
                *step = step.as_ref().unwrap().next;
                assert!(z.direction.get() != 0.0);
                z.direction.set(0.0);
            } else {

            }
        }
    }

}*/