Directory::searchRange, Directory::entrySelector and Direcoty::rangeShift computation are incorrect

[be5invis]

https://github.com/devongovett/fontkit/blob/master/src/tables/directory.js#L47

Per OTS it should be:

this.searchRange = Math.pow(2, Math.floor(Math.log(this.numTables) / Math.LN2)) * 16;
this.entrySelector = Math.floor(Math.log(this.numTables) / Math.LN2);
this.rangeShift = this.numTables * 16 - this.searchRange;

[Pomax]

The exact text in the spec is:

• searchRange: (Maximum power of 2 <= numTables) x 16.
• entrySelector: Log2(maximum power of 2 <= numTables).
• rangeShift: NumTables x 16 - searchRange.

This gives us a recipe for really small and efficient code:

• _power: the x for which 2**x is the maximum power of 2 <= numTables
• _maxPowerOf2: 2 ** _power
• searchRange: _maxPowerOf2 x 16.
• entrySelector: _power - we already computed this as first operation
• rangeShift: NumTables x 16 - searchRange.

So we can rearrange this:

• entrySelector: (the x for which 2**x is the maximum power of 2 <= numTables)
• searchRange: 2 ** entrySelector x 16.
• rangeShift: NumTables x 16 - searchRange.

Which translates to the following JS, using bit operations rather than arithmetic:

this.entrySelector = (Math.log(this.numTables)/Math.LN2) | 0;
let maxPowerOf2 = 1 << this.entrySelector;
this.searchRange = maxPowerOf2 << 4;
this.rangeShift = this.numTables << 4 - this.searchRange

(We know that the |0 is a safe operation here, because entrySelector is a uint16, whereas ...|0 is a uint32 operation in JS)

And of course if we want more verbosity:

this.entrySelector = Math.floor((Math.log(this.numTables)/Math.LN2));
let maxPowerOf2 = 2 ** this.entrySelector;
this.searchRange = maxPowerOf2 * 16;
this.rangeShift = this.numTables * 16<< 4 - this.searchRange

[be5invis]

So OTS, FontForge, TTX and OTFCC are all wrong? @behdad

发自我的 iPhone

在 2018年4月24日，01:57，Pomax notifications@github.com<mailto:notifications@github.com> 写道：

The exact text in the spechttps://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdocs.microsoft.com%2Fen-us%2Ftypography%2Fopentype%2Fspec%2Ffont-file%23organization-of-an-opentype-font&data=02%7C01%7C%7C4ba9e059a9d04d86106508d5a943a236%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636601030309505754&sdata=GGc0iMKseP3jpm2KXaf0j3NEZD2ejvyCaLleGe%2FzoiQ%3D&reserved=0 is:

• searchRange: (Maximum power of 2 <= numTables) x 16.
• entrySelector: Log2(maximum power of 2 <= numTables).
• rangeShift: NumTables x 16 - searchRange.

This gives us a recipe for really small and efficient code:

• _power: the x for which 2**x is the maximum power of 2 <= numTables
• _maxPowerOf2: 2 ** _power
• searchRange: _maxPowerOf2 x 16.
• entrySelector: _power - we already computed this as first operation
• rangeShift: NumTables x 16 - searchRange.

So we can rearrange this:

• entrySelector: (the x for which 2**x is the maximum power of 2 <= numTables)
• searchRange: 2 ** entrySelector x 16.
• rangeShift: NumTables x 16 - searchRange.

Which translates to the following JS, using bit operations rather than arithmetic:

this.entrySelector = (Math.log(this.numTables)/Math.LN2) | 0; let maxPowerOf2 = 1 << this.entrySelector; this.searchRange = maxPowerOf2 << 4; this.rangeShift = this.numTables << 4 - this.searchRange

(We know that the |0 is a safe operation here, because entrySelector is a uint16, whereas ...|0 is a uint32 operation in JS)

And of course if we want more verbosity:

this.entrySelector = Math.floor((Math.log(this.numTables)/Math.LN2)); let maxPowerOf2 = 2 * this.entrySelector; this.searchRange = maxPowerOf2 16; this.rangeShift = this.numTables * 16<< 4 - this.searchRange

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHubhttps://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fdevongovett%2Ffontkit%2Fissues%2F160%23issuecomment-383666204&data=02%7C01%7C%7C4ba9e059a9d04d86106508d5a943a236%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636601030309505754&sdata=D6C7WrrKYVEacQRdgnp%2BEP04ZfowW7sPPVIzsMG7%2Fe8%3D&reserved=0, or mute the threadhttps://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FAAOp26bkO__idQpfCCpyGrpLebiUCdblks5trhX0gaJpZM4Teg-B&data=02%7C01%7C%7C4ba9e059a9d04d86106508d5a943a236%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636601030309505754&sdata=%2Ferf4SP0%2BQTUF8uwVRkYLxPUC3UVxUnXpQ236reZ2lk%3D&reserved=0.

[be5invis]

searchRange: (Maximum power of 2 <= numTables) x 16. I think it means that “Maximum integer that having the form 2**x where x is an integer.”

[behdad]

So OTS, FontForge, TTX and OTFCC are all wrong? @behdad

Why?

[be5invis]

@behdad I mean that the current implementation in these libs are current. IIf Pomax think his answer is OK then all other libraries are wrong.

[behdad]

I don't understand. Both look correct to me. Which part am I missing?

[be5invis]

@behdad So we need some clarification... to figure out which side (Fontkit vs OTS) is correct. Currently only Fontkit is unique. Other libraries are consistent with OTS.

[behdad]

What's different about it? I've been staying at this code, and I don't see what you mean. It looks equivalent to OTS and TTX codes.

[be5invis]

@behdad Fontkit's code:

function calc_FK() {
    this.searchRange = Math.floor(Math.log(this.numTables) / Math.LN2) * 16;
    this.entrySelector = Math.floor(this.searchRange / Math.LN2);
    this.rangeShift = this.numTables * 16 - this.searchRange;
    return this;
}

OTS, TTX, FontForge, OTFCC... 's code:

function calc_OTS() {
    this.searchRange = Math.pow(2, Math.floor(Math.log(this.numTables) / Math.LN2)) * 16;
    this.entrySelector = Math.floor(Math.log(this.numTables) / Math.LN2);
    this.rangeShift = this.numTables * 16 - this.searchRange;
    return this;
}

The difference:

calc_FK.call({numTables: 23})
// => {numTables: 23, searchRange: 64, entrySelector: 92, rangeShift: 304}
calc_OTS.call({numTables: 23})
// => {numTables: 23, searchRange: 256, entrySelector: 4, rangeShift: 112}

[behdad]

IIf Pomax think his answer is OK then all other libraries are wrong.

Pomax's code looks right to me, and consistent with other libraries:

 this.entrySelector = Math.floor((Math.log(this.numTables)/Math.LN2));
 let maxPowerOf2 = 2 ** this.entrySelector;
 this.searchRange = maxPowerOf2 * 16;
 this.rangeShift = this.numTables * 16<< 4 - this.searchRange 

this is not what you show in calc_FK though. Yes, calc_FK is wrong.

[be5invis]

Closed per #178.