Re: [Devel] Using hashes in FT2 code

[David Turner]

Hi Tom,

  I don't have a solution to the problem you described. However,
  I'd like to advocate a different approach:

  why not simply use a sorted table and perform binary searches ?

  Each table element would contain a "CID => GID" or "SID => GID"
  mapping, and the elements would be ordered by CID or SID

  setting up the table is simple, and it would have a reasonable
  footprint with the ability to work with any kind of encoding..
  with lookups in O(log(n))..


  Moreover, let me remind you that a charmap cache was recently
  introduced in the cache sub-system. Its design is basic but its
  performance is extremely good (when hit), since it simply
  stores in each cache node the glyph indices of 128 consecutive 
  "character codes"

  the combination of these two elements would provide both
  high performance and controlled footprint for what you need.

  and in the case where you wouldn't want to use the cache
  sub-system, performance wouldn't be that bad after all..


Comments ??

- David


Tom Kacvinsky a écrit :
> 
> I am working on a problem for CID keyed CFF fonts.  The basic issues is 
> fidning
> an economical way of storing the CharSet table, which according to the CFF
> specification is the where the mapping between glyph indices and CIDs are
> stored.
> 
> Currently, the array where the CharSet information is stored is indexed by 
> GID,
> and its values are SIDs (for non CID keyed fonts) and CIDs (for CID keyed
> fonts).  I would like to store values index by CIDs/SIDs, the values being the
> GID.
> 
> In order to do this, I need a hash function that always maps a given SID/CID
> into the range 0 to num_glpyhs - 1.  Any ideas on how to best achieve this (I
> haven't coded hash tables in LONG time, so forgive my newbie-ish question).
> 
> Anyway, such a hash function would need to be tied to a certian font, because
> the num_glyphs value changes from font to font.  This, I suspect, will be the
> magor difficulty, because such a function would need to be built on the fly.
> 
> But, if such a function is feasible, we then have a quick way of looking up 
> GIDs
> based on a given CID,a nd the storeage would be economical.
> 
> Any ideas on this train of thought?
> 
> Thanks,
> 
> Tom
> 
> _______________________________________________
> Devel mailing list
> address@hidden
> http://www.freetype.org/mailman/listinfo/devel