michael@0: /*  GRAPHITE2 LICENSING
michael@0: 
michael@0:     Copyright 2010, SIL International
michael@0:     All rights reserved.
michael@0: 
michael@0:     This library is free software; you can redistribute it and/or modify
michael@0:     it under the terms of the GNU Lesser General Public License as published
michael@0:     by the Free Software Foundation; either version 2.1 of License, or
michael@0:     (at your option) any later version.
michael@0: 
michael@0:     This program is distributed in the hope that it will be useful,
michael@0:     but WITHOUT ANY WARRANTY; without even the implied warranty of
michael@0:     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
michael@0:     Lesser General Public License for more details.
michael@0: 
michael@0:     You should also have received a copy of the GNU Lesser General Public
michael@0:     License along with this library in the file named "LICENSE".
michael@0:     If not, write to the Free Software Foundation, 51 Franklin Street, 
michael@0:     Suite 500, Boston, MA 02110-1335, USA or visit their web page on the 
michael@0:     internet at http://www.fsf.org/licenses/lgpl.html.
michael@0: 
michael@0: Alternatively, the contents of this file may be used under the terms of the
michael@0: Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public
michael@0: License, as published by the Free Software Foundation, either version 2
michael@0: of the License or (at your option) any later version.
michael@0: */
michael@0: #include "inc/UtfCodec.h"
michael@0: #include <cstring>
michael@0: #include <cstdlib>
michael@0: 
michael@0: #include "inc/bits.h"
michael@0: #include "inc/Segment.h"
michael@0: #include "graphite2/Font.h"
michael@0: #include "inc/CharInfo.h"
michael@0: #include "inc/debug.h"
michael@0: #include "inc/Slot.h"
michael@0: #include "inc/Main.h"
michael@0: #include "inc/CmapCache.h"
michael@0: #include "inc/Bidi.h"
michael@0: #include "graphite2/Segment.h"
michael@0: 
michael@0: 
michael@0: using namespace graphite2;
michael@0: 
michael@0: Segment::Segment(unsigned int numchars, const Face* face, uint32 script, int textDir)
michael@0: : m_freeSlots(NULL),
michael@0:   m_freeJustifies(NULL),
michael@0:   m_charinfo(new CharInfo[numchars]),
michael@0:   m_face(face),
michael@0:   m_silf(face->chooseSilf(script)),
michael@0:   m_first(NULL),
michael@0:   m_last(NULL),
michael@0:   m_bufSize(numchars + 10),
michael@0:   m_numGlyphs(numchars),
michael@0:   m_numCharinfo(numchars),
michael@0:   m_passBits(m_silf->aPassBits() ? -1 : 0),
michael@0:   m_defaultOriginal(0),
michael@0:   m_dir(textDir)
michael@0: {
michael@0:     freeSlot(newSlot());
michael@0:     m_bufSize = log_binary(numchars)+1;
michael@0: }
michael@0: 
michael@0: Segment::~Segment()
michael@0: {
michael@0:     for (SlotRope::iterator i = m_slots.begin(); i != m_slots.end(); ++i)
michael@0:         free(*i);
michael@0:     for (AttributeRope::iterator j = m_userAttrs.begin(); j != m_userAttrs.end(); ++j)
michael@0:         free(*j);
michael@0:     delete[] m_charinfo;
michael@0: }
michael@0: 
michael@0: #ifndef GRAPHITE2_NSEGCACHE
michael@0: SegmentScopeState Segment::setScope(Slot * firstSlot, Slot * lastSlot, size_t subLength)
michael@0: {
michael@0:     SegmentScopeState state;
michael@0:     state.numGlyphsOutsideScope = m_numGlyphs - subLength;
michael@0:     state.realFirstSlot = m_first;
michael@0:     state.slotBeforeScope = firstSlot->prev();
michael@0:     state.slotAfterScope = lastSlot->next();
michael@0:     state.realLastSlot = m_last;
michael@0:     firstSlot->prev(NULL);
michael@0:     lastSlot->next(NULL);
michael@0:     assert(m_defaultOriginal == 0);
michael@0:     m_defaultOriginal = firstSlot->original();
michael@0:     m_numGlyphs = subLength;
michael@0:     m_first = firstSlot;
michael@0:     m_last = lastSlot;
michael@0:     return state;
michael@0: }
michael@0: 
michael@0: void Segment::removeScope(SegmentScopeState & state)
michael@0: {
michael@0:     m_numGlyphs = state.numGlyphsOutsideScope + m_numGlyphs;
michael@0:     if (state.slotBeforeScope)
michael@0:     {
michael@0:         state.slotBeforeScope->next(m_first);
michael@0:         m_first->prev(state.slotBeforeScope);
michael@0:         m_first = state.realFirstSlot;
michael@0:     }
michael@0:     if (state.slotAfterScope)
michael@0:     {
michael@0:         state.slotAfterScope->prev(m_last);
michael@0:         m_last->next(state.slotAfterScope);
michael@0:         m_last = state.realLastSlot;
michael@0:     }
michael@0:     m_defaultOriginal = 0;
michael@0: }
michael@0: 
michael@0: #if 0
michael@0: void Segment::append(const Segment &other)
michael@0: {
michael@0:     Rect bbox = other.m_bbox + m_advance;
michael@0: 
michael@0:     m_slots.insert(m_slots.end(), other.m_slots.begin(), other.m_slots.end());
michael@0:     CharInfo* pNewCharInfo = new CharInfo[m_numCharinfo+other.m_numCharinfo];       //since CharInfo has no constructor, this doesn't do much
michael@0:     for (unsigned int i=0 ; i<m_numCharinfo ; ++i)
michael@0:     pNewCharInfo[i] = m_charinfo[i];
michael@0:     m_last->next(other.m_first);
michael@0:     other.m_last->prev(m_last);
michael@0:     m_userAttrs.insert(m_userAttrs.end(), other.m_userAttrs.begin(), other.m_userAttrs.end());
michael@0:     
michael@0:     delete[] m_charinfo;
michael@0:     m_charinfo = pNewCharInfo;
michael@0:     pNewCharInfo += m_numCharinfo ;
michael@0:     for (unsigned int i=0 ; i<m_numCharinfo ; ++i)
michael@0:         pNewCharInfo[i] = other.m_charinfo[i];
michael@0:  
michael@0:     m_numCharinfo += other.m_numCharinfo;
michael@0:     m_numGlyphs += other.m_numGlyphs;
michael@0:     m_advance = m_advance + other.m_advance;
michael@0:     m_bbox = m_bbox.widen(bbox);
michael@0:     m_passBits &= other.passBits();
michael@0: }
michael@0: #endif
michael@0: #endif // GRAPHITE2_NSEGCACHE
michael@0: 
michael@0: void Segment::appendSlot(int id, int cid, int gid, int iFeats, size_t coffset)
michael@0: {
michael@0:     Slot *aSlot = newSlot();
michael@0:     
michael@0:     if (!aSlot) return;
michael@0:     m_charinfo[id].init(cid);
michael@0:     m_charinfo[id].feats(iFeats);
michael@0:     m_charinfo[id].base(coffset);
michael@0:     const GlyphFace * theGlyph = m_face->glyphs().glyphSafe(gid);
michael@0:     m_charinfo[id].breakWeight(theGlyph ? theGlyph->attrs()[m_silf->aBreak()] : 0);
michael@0:     
michael@0:     aSlot->child(NULL);
michael@0:     aSlot->setGlyph(this, gid, theGlyph);
michael@0:     aSlot->originate(id);
michael@0:     aSlot->before(id);
michael@0:     aSlot->after(id);
michael@0:     if (m_last) m_last->next(aSlot);
michael@0:     aSlot->prev(m_last);
michael@0:     m_last = aSlot;
michael@0:     if (!m_first) m_first = aSlot;
michael@0:     if (theGlyph && m_silf->aPassBits())
michael@0:         m_passBits &= theGlyph->attrs()[m_silf->aPassBits()] 
michael@0:                     | (m_silf->numPasses() > 16 ? (theGlyph->attrs()[m_silf->aPassBits() + 1] << 16) : 0);
michael@0: }
michael@0: 
michael@0: Slot *Segment::newSlot()
michael@0: {
michael@0:     if (!m_freeSlots)
michael@0:     {
michael@0:         int numUser = m_silf->numUser();
michael@0: #if !defined GRAPHITE2_NTRACING
michael@0:         if (m_face->logger()) ++numUser;
michael@0: #endif
michael@0:         Slot *newSlots = grzeroalloc<Slot>(m_bufSize);
michael@0:         int16 *newAttrs = grzeroalloc<int16>(numUser * m_bufSize);
michael@0:         if (!newSlots || !newAttrs) return NULL;
michael@0:         for (size_t i = 0; i < m_bufSize; i++)
michael@0:         {
michael@0:             newSlots[i].next(newSlots + i + 1);
michael@0:             newSlots[i].userAttrs(newAttrs + i * numUser);
michael@0:             newSlots[i].setBidiClass(-1);
michael@0:         }
michael@0:         newSlots[m_bufSize - 1].next(NULL);
michael@0:         newSlots[0].next(NULL);
michael@0:         m_slots.push_back(newSlots);
michael@0:         m_userAttrs.push_back(newAttrs);
michael@0:         m_freeSlots = (m_bufSize > 1)? newSlots + 1 : NULL;
michael@0:         return newSlots;
michael@0:     }
michael@0:     Slot *res = m_freeSlots;
michael@0:     m_freeSlots = m_freeSlots->next();
michael@0:     res->next(NULL);
michael@0:     return res;
michael@0: }
michael@0: 
michael@0: void Segment::freeSlot(Slot *aSlot)
michael@0: {
michael@0:     if (m_last == aSlot) m_last = aSlot->prev();
michael@0:     if (m_first == aSlot) m_first = aSlot->next();
michael@0:     if (aSlot->attachedTo())
michael@0:         aSlot->attachedTo()->removeChild(aSlot);
michael@0:     while (aSlot->firstChild())
michael@0:     {
michael@0:         aSlot->firstChild()->attachTo(NULL);
michael@0:         aSlot->removeChild(aSlot->firstChild());
michael@0:     }
michael@0:     // reset the slot incase it is reused
michael@0:     ::new (aSlot) Slot;
michael@0:     memset(aSlot->userAttrs(), 0, m_silf->numUser() * sizeof(int16));
michael@0:     // Update generation counter for debug
michael@0: #if !defined GRAPHITE2_NTRACING
michael@0:     if (m_face->logger())
michael@0:         ++aSlot->userAttrs()[m_silf->numUser()];
michael@0: #endif
michael@0:     // update next pointer
michael@0:     if (!m_freeSlots)
michael@0:         aSlot->next(NULL);
michael@0:     else
michael@0:         aSlot->next(m_freeSlots);
michael@0:     m_freeSlots = aSlot;
michael@0: }
michael@0: 
michael@0: SlotJustify *Segment::newJustify()
michael@0: {
michael@0:     if (!m_freeJustifies)
michael@0:     {
michael@0:         const size_t justSize = SlotJustify::size_of(m_silf->numJustLevels());
michael@0:         byte *justs = grzeroalloc<byte>(justSize * m_bufSize);
michael@0:         if (!justs) return NULL;
michael@0:         for (int i = m_bufSize - 2; i >= 0; --i)
michael@0:         {
michael@0:             SlotJustify *p = reinterpret_cast<SlotJustify *>(justs + justSize * i);
michael@0:             SlotJustify *next = reinterpret_cast<SlotJustify *>(justs + justSize * (i + 1));
michael@0:             p->next = next;
michael@0:         }
michael@0:         m_freeJustifies = (SlotJustify *)justs;
michael@0:         m_justifies.push_back(m_freeJustifies);
michael@0:     }
michael@0:     SlotJustify *res = m_freeJustifies;
michael@0:     m_freeJustifies = m_freeJustifies->next;
michael@0:     res->next = NULL;
michael@0:     return res;
michael@0: }
michael@0: 
michael@0: void Segment::freeJustify(SlotJustify *aJustify)
michael@0: {
michael@0:     int numJust = m_silf->numJustLevels();
michael@0:     if (m_silf->numJustLevels() <= 0) numJust = 1;
michael@0:     aJustify->next = m_freeJustifies;
michael@0:     memset(aJustify->values, 0, numJust*SlotJustify::NUMJUSTPARAMS*sizeof(int16));
michael@0:     m_freeJustifies = aJustify;
michael@0: }
michael@0: 
michael@0: #ifndef GRAPHITE2_NSEGCACHE
michael@0: void Segment::splice(size_t offset, size_t length, Slot * const startSlot,
michael@0:                        Slot * endSlot, const Slot * srcSlot,
michael@0:                        const size_t numGlyphs)
michael@0: {
michael@0:     size_t numChars = length;
michael@0:     extendLength(numGlyphs - length);
michael@0:     // remove any extra
michael@0:     if (numGlyphs < length)
michael@0:     {
michael@0:         Slot * end = endSlot->next();
michael@0:         do
michael@0:         {
michael@0:             endSlot = endSlot->prev();
michael@0:             freeSlot(endSlot->next());
michael@0:         } while (numGlyphs < --length);
michael@0:         endSlot->next(end);
michael@0:         if (end)
michael@0:             end->prev(endSlot);
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         // insert extra slots if needed
michael@0:         while (numGlyphs > length)
michael@0:         {
michael@0:             Slot * extra = newSlot();
michael@0:             if (!extra) return;
michael@0:             extra->prev(endSlot);
michael@0:             extra->next(endSlot->next());
michael@0:             endSlot->next(extra);
michael@0:             if (extra->next())
michael@0:                 extra->next()->prev(extra);
michael@0:             if (m_last == endSlot)
michael@0:                 m_last = extra;
michael@0:             endSlot = extra;
michael@0:             ++length;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     endSlot = endSlot->next();
michael@0:     assert(numGlyphs == length);
michael@0:     assert(offset + numChars <= m_numCharinfo);
michael@0:     Slot * indexmap[eMaxSpliceSize*3];
michael@0:     assert(numGlyphs < sizeof indexmap/sizeof *indexmap);
michael@0:     Slot * slot = startSlot;
michael@0:     for (uint16 i=0; i < numGlyphs; slot = slot->next(), ++i)
michael@0:         indexmap[i] = slot;
michael@0: 
michael@0:     for (slot = startSlot; slot != endSlot; slot = slot->next(), srcSlot = srcSlot->next())
michael@0:     {
michael@0:         slot->set(*srcSlot, offset, m_silf->numUser(), m_silf->numJustLevels(), numChars);
michael@0:         if (srcSlot->attachedTo())  slot->attachTo(indexmap[srcSlot->attachedTo()->index()]);
michael@0:         if (srcSlot->nextSibling()) slot->m_sibling = indexmap[srcSlot->nextSibling()->index()];
michael@0:         if (srcSlot->firstChild())  slot->m_child = indexmap[srcSlot->firstChild()->index()];
michael@0:     }
michael@0: }
michael@0: #endif // GRAPHITE2_NSEGCACHE
michael@0: 
michael@0: void Segment::linkClusters(Slot *s, Slot * end)
michael@0: {
michael@0:     end = end->next();
michael@0: 
michael@0:     for (; s != end && !s->isBase(); s = s->next());
michael@0:     Slot * ls = s;
michael@0: 
michael@0:     if (m_dir & 1)
michael@0:     {
michael@0:         for (; s != end; s = s->next())
michael@0:         {
michael@0:             if (!s->isBase())   continue;
michael@0: 
michael@0:             s->sibling(ls);
michael@0:             ls = s;
michael@0:         }
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         for (; s != end; s = s->next())
michael@0:         {
michael@0:             if (!s->isBase())   continue;
michael@0: 
michael@0:             ls->sibling(s);
michael@0:             ls = s;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: Position Segment::positionSlots(const Font *font, Slot * iStart, Slot * iEnd)
michael@0: {
michael@0:     Position currpos(0., 0.);
michael@0:     float clusterMin = 0.;
michael@0:     Rect bbox;
michael@0: 
michael@0:     if (!iStart)    iStart = m_first;
michael@0:     if (!iEnd)      iEnd   = m_last;
michael@0: 
michael@0:     if (m_dir & 1)
michael@0:     {
michael@0:         for (Slot * s = iEnd, * const end = iStart->prev(); s && s != end; s = s->prev())
michael@0:         {
michael@0:             if (s->isBase())
michael@0:                 currpos = s->finalise(this, font, currpos, bbox, 0, clusterMin = currpos.x);
michael@0:         }
michael@0:     }
michael@0:     else
michael@0:     {
michael@0:         for (Slot * s = iStart, * const end = iEnd->next(); s && s != end; s = s->next())
michael@0:         {
michael@0:             if (s->isBase())
michael@0:                 currpos = s->finalise(this, font, currpos, bbox, 0, clusterMin = currpos.x);
michael@0:         }
michael@0:     }
michael@0:     return currpos;
michael@0: }
michael@0: 
michael@0: 
michael@0: void Segment::associateChars(int offset, int numChars)
michael@0: {
michael@0:     int i = 0, j = 0;
michael@0:     CharInfo *c, *cend;
michael@0:     for (c = m_charinfo + offset, cend = m_charinfo + offset + numChars; c != cend; ++c)
michael@0:     {
michael@0:         c->before(-1);
michael@0:         c->after(-1);
michael@0:     }
michael@0:     for (Slot * s = m_first; s; s->index(i++), s = s->next())
michael@0:     {
michael@0:         j = s->before();
michael@0:         if (j < 0)  continue;
michael@0: 
michael@0:         for (const int after = s->after(); j <= after; ++j)
michael@0:         {
michael@0:             c = charinfo(j);
michael@0:             if (c->before() == -1 || i < c->before())   c->before(i);
michael@0:             if (c->after() < i)                         c->after(i);
michael@0:         }
michael@0:     }
michael@0:     for (Slot *s = m_first; s; s = s->next())
michael@0:     {
michael@0:         int a;
michael@0:         for (a = s->after() + 1; a < offset + numChars && charinfo(a)->after() < 0; ++a)
michael@0:         { charinfo(a)->after(s->index()); }
michael@0:         --a;
michael@0:         s->after(a);
michael@0: 
michael@0:         for (a = s->before() - 1; a >= offset && charinfo(a)->before() < 0; --a)
michael@0:         { charinfo(a)->before(s->index()); }
michael@0:         ++a;
michael@0:         s->before(a);
michael@0:     }
michael@0: }
michael@0: 
michael@0: 
michael@0: template <typename utf_iter>
michael@0: inline void process_utf_data(Segment & seg, const Face & face, const int fid, utf_iter c, size_t n_chars)
michael@0: {
michael@0:     const Cmap    & cmap = face.cmap();
michael@0:     int slotid = 0;
michael@0: 
michael@0:     const typename utf_iter::codeunit_type * const base = c;
michael@0:     for (; n_chars; --n_chars, ++c, ++slotid)
michael@0:     {
michael@0:         const uint32 usv = *c;
michael@0:         uint16 gid = cmap[usv];
michael@0:         if (!gid)   gid = face.findPseudo(usv);
michael@0:         seg.appendSlot(slotid, usv, gid, fid, c - base);
michael@0:     }
michael@0: }
michael@0: 
michael@0: 
michael@0: bool Segment::read_text(const Face *face, const Features* pFeats/*must not be NULL*/, gr_encform enc, const void* pStart, size_t nChars)
michael@0: {
michael@0:     assert(face);
michael@0:     assert(pFeats);
michael@0:     if (!m_charinfo) return false;
michael@0: 
michael@0:     // utf iterator is self recovering so we don't care about the error state of the iterator.
michael@0:     switch (enc)
michael@0:     {
michael@0:     case gr_utf8:   process_utf_data(*this, *face, addFeatures(*pFeats), utf8::const_iterator(pStart), nChars); break;
michael@0:     case gr_utf16:  process_utf_data(*this, *face, addFeatures(*pFeats), utf16::const_iterator(pStart), nChars); break;
michael@0:     case gr_utf32:  process_utf_data(*this, *face, addFeatures(*pFeats), utf32::const_iterator(pStart), nChars); break;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void Segment::prepare_pos(const Font * /*font*/)
michael@0: {
michael@0:     // copy key changeable metrics into slot (if any);
michael@0: }
michael@0: 
michael@0: Slot *process_bidi(Slot *start, int level, int prelevel, int &nextLevel, int dirover, int isol, int &cisol, int &isolerr, int &embederr, int init, Segment *seg, uint8 aMirror, BracketPairStack &stack);
michael@0: void resolveImplicit(Slot *s, Segment *seg, uint8 aMirror);
michael@0: void resolveWhitespace(int baseLevel, Slot *s);
michael@0: Slot *resolveOrder(Slot * & s, const bool reordered, const int level = 0);
michael@0: 
michael@0: void Segment::bidiPass(uint8 aBidi, int paradir, uint8 aMirror)
michael@0: {
michael@0:     if (slotCount() == 0)
michael@0:         return;
michael@0: 
michael@0:     Slot *s;
michael@0:     int baseLevel = paradir ? 1 : 0;
michael@0:     unsigned int bmask = 0;
michael@0:     unsigned int ssize = 0;
michael@0:     for (s = first(); s; s = s->next())
michael@0:     {
michael@0:         if (s->getBidiClass() == -1)
michael@0:         {
michael@0:             unsigned int bAttr = glyphAttr(s->gid(), aBidi);
michael@0:             s->setBidiClass((bAttr <= 22) * bAttr);
michael@0:         }
michael@0:         bmask |= (1 << s->getBidiClass());
michael@0:         s->setBidiLevel(baseLevel);
michael@0:         if (glyphAttr(s->gid(), aMirror) && s->getBidiClass() == 21)
michael@0:             ++ssize;
michael@0:     }
michael@0: 
michael@0:     BracketPairStack bstack(ssize);
michael@0:     if (bmask & (paradir ? 0x2E7892 : 0x2E789C))
michael@0:     {
michael@0:         // O(8N) algorithm, with no working data beyond what is needed for processParens
michael@0:         int nextLevel = paradir;
michael@0:         int e, i, c;
michael@0:         process_bidi(first(), baseLevel, paradir, nextLevel, 0, 0, c = 0, i = 0, e = 0, 1, this, aMirror, bstack);
michael@0:         resolveImplicit(first(), this, aMirror);
michael@0:         resolveWhitespace(baseLevel, last());
michael@0:         s = resolveOrder(s = first(), baseLevel != 0);
michael@0:         if (s)
michael@0:         {
michael@0:             first(s); last(s->prev());
michael@0:             s->prev()->next(0); s->prev(0);
michael@0:         }
michael@0:     }
michael@0:     else if (!(dir() & 4) && baseLevel && aMirror)
michael@0:     {
michael@0:         for (s = first(); s; s = s->next())
michael@0:         {
michael@0:             unsigned short g = glyphAttr(s->gid(), aMirror);
michael@0:             if (g) s->setGlyph(this, g);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: