With humungous thanks to Hauke for ideas, suggestions, algorithms, inspriation, etc., I've got the first version of etc.unicode uploaded to Deimos. It gives you access to pretty much all Unicode properties. For an idea of the flavor of the thing, these are the functions you get:

char[]              getAge(dchar c)
char[]              getArabicShapingName(dchar c)
BidiClass           getBidiClass(dchar c)
char[]              getBidiClassName(BidiClass e)
char[]              getBidiClassName(dchar c)
dchar               getBidiMirroringGlyph(dchar c)
char[]              getBlock(dchar c)
uint                getCanonicalCombiningClass(dchar c)
int                 getDecimalDigit(dchar c)
wchar[]             getDecompositionMappingUTF16(dchar c)
dchar[]             getDecompositionMappingUTF32(dchar c)
char[]              getDecompositionMappingUTF8(dchar c)
DecompositionType   getDecompositionType(dchar c)
char[]              getDecompositionTypeName(DecompositionType e)
char[]              getDecompositionTypeName(dchar c)
int                 getDigit(dchar c)
EastAsianWidth      getEastAsianWidth(dchar c)
char[]              getEastAsianWidthName(EastAsianWidth e)
char[]              getEastAsianWidthName(dchar c)
GeneralCategory     getGeneralCategory(dchar c)
char[]              getGeneralCategoryName(GeneralCategory e)
char[]              getGeneralCategoryName(dchar c)
HangulSyllableType  getHangulSyllableType(dchar c)
char[]              getHangulSyllableTypeName(HangulSyllableType e)
char[]              getHangulSyllableTypeName(dchar c)
int                 getHexValue(dchar c)
char[]              getISOComment(dchar c)
char[]              getJamo(dchar c)
char[]              getJoiningGroup(dchar c)
JoiningType         getJoiningType(dchar c)
char[]              getJoiningTypeName(JoiningType e)
char[]              getJoiningTypeName(dchar c)
LineBreak           getLineBreak(dchar c)
char[]              getLineBreakName(LineBreak e)
char[]              getLineBreakName(dchar c)
wchar[]             getLowercaseMappingLocalUTF16(dchar c, char[] locale)
dchar[]             getLowercaseMappingLocalUTF32(dchar c, char[] locale)
char[]              getLowercaseMappingLocalUTF8(dchar c, char[] locale)
wchar[]             getLowercaseMappingUTF16(dchar c)
dchar[]             getLowercaseMappingUTF32(dchar c)
char[]              getLowercaseMappingUTF8(dchar c)
char[]              getName(dchar c)
char[]              getNormalizationCorrectionVersion(dchar c)
dchar               getNormalizationCorrectionsCorrection(dchar c)
dchar               getNormalizationCorrectionsOriginal(dchar c)
char[]              getNumeric(dchar c)
uint                getNumericType(dchar c)
Script              getScript(dchar c)
char[]              getScriptName(Script e)
char[]              getScriptName(dchar c)
dchar               getSimpleCaseFolding(dchar c)
dchar               getSimpleLowercaseMapping(dchar c)
dchar               getSimpleTitlecaseMapping(dchar c)
dchar               getSimpleUppercaseMapping(dchar c)
char[]              getSpecialCaseCondition(dchar c)
char[]              getSpecialCaseConditionLocal(dchar c)
wchar[]             getTitlecaseMappingLocalUTF16(dchar c, char[] locale)
dchar[]             getTitlecaseMappingLocalUTF32(dchar c, char[] locale)
char[]              getTitlecaseMappingLocalUTF8(dchar c, char[] locale)
wchar[]             getTitlecaseMappingUTF16(dchar c)
dchar[]             getTitlecaseMappingUTF32(dchar c)
char[]              getTitlecaseMappingUTF8(dchar c)
char[]              getUnicode1Name(dchar c)
wchar[]             getUppercaseMappingLocalUTF16(dchar c, char[] locale)
dchar[]             getUppercaseMappingLocalUTF32(dchar c, char[] locale)
char[]              getUppercaseMappingLocalUTF8(dchar c, char[] locale)
wchar[]             getUppercaseMappingUTF16(dchar c)
dchar[]             getUppercaseMappingUTF32(dchar c)
char[]              getUppercaseMappingUTF8(dchar c)
bool                isASCIIHexDigit(dchar c)
bool                isAlphabetic(dchar c)
bool                isBidiControl(dchar c)
bool                isBidiMirrored(dchar c)
bool                isCompositionExclusion(dchar c)
bool                isDash(dchar c)
bool                isDefaultIgnorableCodePoint(dchar c)
bool                isDeprecated(dchar c)
bool                isDiacritic(dchar c)
bool                isExtender(dchar c)
bool                isGraphemeBase(dchar c)
bool                isGraphemeExtend(dchar c)
bool                isGraphemeLink(dchar c)
bool                isHexDigit(dchar c)
bool                isHyphen(dchar c)
bool                isIDContinue(dchar c)
bool                isIDSBinaryOperator(dchar c)
bool                isIDSTrinaryOperator(dchar c)
bool                isIDStart(dchar c)
bool                isIdeographic(dchar c)
bool                isJoinControl(dchar c)
bool                isLogicalOrderException(dchar c)
bool                isLowercase(dchar c)
bool                isMath(dchar c)
bool                isNoncharacterCodePoint(dchar c)
bool                isOtherAlphabetic(dchar c)
bool                isOtherDefaultIgnorableCodePoint(dchar c)
bool                isOtherGraphemeExtend(dchar c)
bool                isOtherIDStart(dchar c)
bool                isOtherLowercase(dchar c)
bool                isOtherMath(dchar c)
bool                isOtherUppercase(dchar c)
bool                isQuotationMark(dchar c)
bool                isRadical(dchar c)
bool                isSTerm(dchar c)
bool                isSoftDotted(dchar c)
bool                isTerminalPunctuation(dchar c)
bool                isUnifiedIdeograph(dchar c)
bool                isUppercase(dchar c)
bool                isVariationSelector(dchar c)
bool                isWhiteSpace(dchar c)
bool                isXIDContinue(dchar c)
bool                isXIDStart(dchar c)

Pretty much every function is in its own module. This means that when you link against it you only get those functions which you actually call. In addition, the tables that get linked in are tiny (well, most of them), and in some cases even non-existent, thanks to some seriously aggressive space optimization. For instance, if you call toSimpleUppercaseMapping(), which converts a character to uppercase, you will add only 5K to the size of your executable.

Despite this space saving, the functions should still be pretty fast. The code for that uppercasing function consists of two if tests, a shift, a switch statement with seven cases, and a table lookup. And nothing else.

Most of the other functions go the same way. Some are optimized in different ways, but I believe we now have a very good balance between speed and size.

This is only the first step toward full Unicode support for D. Character properties are the heart of the Unicode algorithms. You need those first - so here they are.

Currently, Deimos is not very well organized, so my next task will be trying to get that together. There are lots of interesting things in Deimos now (and some of them I don't even know what they are), but what we're lacking is overall organization, a build script, a "ready-to-go" downloadable library, proper doxygen documentation, and so on. It's a bit irritating, so I guess now is the time to deal with that. In the meantime, you can download the etc.unicode source files and documentation and build-it-yourself. (But be patient. There are A LOT of files to compile).

Arcane Jill

Cool! Is this a supplement or a replacement for Hauke's earlier work?

This is incredible!

Hopefully I'll have some free time next week to check this out :).

Great work.

Hauke



Arcane Jill wrote:
> With humungous thanks to Hauke for ideas, suggestions, algorithms, inspriation,
> etc., I've got the first version of etc.unicode uploaded to Deimos. It gives you
> access to pretty much all Unicode properties. For an idea of the flavor of the
> thing, these are the functions you get:
> 
> char[]              getAge(dchar c)
> char[]              getArabicShapingName(dchar c)
> BidiClass           getBidiClass(dchar c)
> char[]              getBidiClassName(BidiClass e)
> char[]              getBidiClassName(dchar c)
> dchar               getBidiMirroringGlyph(dchar c)
> char[]              getBlock(dchar c)
> uint                getCanonicalCombiningClass(dchar c)
> int                 getDecimalDigit(dchar c)
> wchar[]             getDecompositionMappingUTF16(dchar c)
> dchar[]             getDecompositionMappingUTF32(dchar c)
> char[]              getDecompositionMappingUTF8(dchar c)
> DecompositionType   getDecompositionType(dchar c)
> char[]              getDecompositionTypeName(DecompositionType e)
> char[]              getDecompositionTypeName(dchar c)
> int                 getDigit(dchar c)
> EastAsianWidth      getEastAsianWidth(dchar c)
> char[]              getEastAsianWidthName(EastAsianWidth e)
> char[]              getEastAsianWidthName(dchar c)
> GeneralCategory     getGeneralCategory(dchar c)
> char[]              getGeneralCategoryName(GeneralCategory e)
> char[]              getGeneralCategoryName(dchar c)
> HangulSyllableType  getHangulSyllableType(dchar c)
> char[]              getHangulSyllableTypeName(HangulSyllableType e)
> char[]              getHangulSyllableTypeName(dchar c)
> int                 getHexValue(dchar c)
> char[]              getISOComment(dchar c)
> char[]              getJamo(dchar c)
> char[]              getJoiningGroup(dchar c)
> JoiningType         getJoiningType(dchar c)
> char[]              getJoiningTypeName(JoiningType e)
> char[]              getJoiningTypeName(dchar c)
> LineBreak           getLineBreak(dchar c)
> char[]              getLineBreakName(LineBreak e)
> char[]              getLineBreakName(dchar c)
> wchar[]             getLowercaseMappingLocalUTF16(dchar c, char[] locale)
> dchar[]             getLowercaseMappingLocalUTF32(dchar c, char[] locale)
> char[]              getLowercaseMappingLocalUTF8(dchar c, char[] locale)
> wchar[]             getLowercaseMappingUTF16(dchar c)
> dchar[]             getLowercaseMappingUTF32(dchar c)
> char[]              getLowercaseMappingUTF8(dchar c)
> char[]              getName(dchar c)
> char[]              getNormalizationCorrectionVersion(dchar c)
> dchar               getNormalizationCorrectionsCorrection(dchar c)
> dchar               getNormalizationCorrectionsOriginal(dchar c)
> char[]              getNumeric(dchar c)
> uint                getNumericType(dchar c)
> Script              getScript(dchar c)
> char[]              getScriptName(Script e)
> char[]              getScriptName(dchar c)
> dchar               getSimpleCaseFolding(dchar c)
> dchar               getSimpleLowercaseMapping(dchar c)
> dchar               getSimpleTitlecaseMapping(dchar c)
> dchar               getSimpleUppercaseMapping(dchar c)
> char[]              getSpecialCaseCondition(dchar c)
> char[]              getSpecialCaseConditionLocal(dchar c)
> wchar[]             getTitlecaseMappingLocalUTF16(dchar c, char[] locale)
> dchar[]             getTitlecaseMappingLocalUTF32(dchar c, char[] locale)
> char[]              getTitlecaseMappingLocalUTF8(dchar c, char[] locale)
> wchar[]             getTitlecaseMappingUTF16(dchar c)
> dchar[]             getTitlecaseMappingUTF32(dchar c)
> char[]              getTitlecaseMappingUTF8(dchar c)
> char[]              getUnicode1Name(dchar c)
> wchar[]             getUppercaseMappingLocalUTF16(dchar c, char[] locale)
> dchar[]             getUppercaseMappingLocalUTF32(dchar c, char[] locale)
> char[]              getUppercaseMappingLocalUTF8(dchar c, char[] locale)
> wchar[]             getUppercaseMappingUTF16(dchar c)
> dchar[]             getUppercaseMappingUTF32(dchar c)
> char[]              getUppercaseMappingUTF8(dchar c)
> bool                isASCIIHexDigit(dchar c)
> bool                isAlphabetic(dchar c)
> bool                isBidiControl(dchar c)
> bool                isBidiMirrored(dchar c)
> bool                isCompositionExclusion(dchar c)
> bool                isDash(dchar c)
> bool                isDefaultIgnorableCodePoint(dchar c)
> bool                isDeprecated(dchar c)
> bool                isDiacritic(dchar c)
> bool                isExtender(dchar c)
> bool                isGraphemeBase(dchar c)
> bool                isGraphemeExtend(dchar c)
> bool                isGraphemeLink(dchar c)
> bool                isHexDigit(dchar c)
> bool                isHyphen(dchar c)
> bool                isIDContinue(dchar c)
> bool                isIDSBinaryOperator(dchar c)
> bool                isIDSTrinaryOperator(dchar c)
> bool                isIDStart(dchar c)
> bool                isIdeographic(dchar c)
> bool                isJoinControl(dchar c)
> bool                isLogicalOrderException(dchar c)
> bool                isLowercase(dchar c)
> bool                isMath(dchar c)
> bool                isNoncharacterCodePoint(dchar c)
> bool                isOtherAlphabetic(dchar c)
> bool                isOtherDefaultIgnorableCodePoint(dchar c)
> bool                isOtherGraphemeExtend(dchar c)
> bool                isOtherIDStart(dchar c)
> bool                isOtherLowercase(dchar c)
> bool                isOtherMath(dchar c)
> bool                isOtherUppercase(dchar c)
> bool                isQuotationMark(dchar c)
> bool                isRadical(dchar c)
> bool                isSTerm(dchar c)
> bool                isSoftDotted(dchar c)
> bool                isTerminalPunctuation(dchar c)
> bool                isUnifiedIdeograph(dchar c)
> bool                isUppercase(dchar c)
> bool                isVariationSelector(dchar c)
> bool                isWhiteSpace(dchar c)
> bool                isXIDContinue(dchar c)
> bool                isXIDStart(dchar c)
> 
> Pretty much every function is in its own module. This means that when you link
> against it you only get those functions which you actually call. In addition,
> the tables that get linked in are tiny (well, most of them), and in some cases
> even non-existent, thanks to some seriously aggressive space optimization. For
> instance, if you call toSimpleUppercaseMapping(), which converts a character to
> uppercase, you will add only 5K to the size of your executable.
> 
> Despite this space saving, the functions should still be pretty fast. The code
> for that uppercasing function consists of two if tests, a shift, a switch
> statement with seven cases, and a table lookup. And nothing else.
> 
> Most of the other functions go the same way. Some are optimized in different
> ways, but I believe we now have a very good balance between speed and size.
> 
> This is only the first step toward full Unicode support for D. Character
> properties are the heart of the Unicode algorithms. You need those first - so
> here they are.
> 
> Currently, Deimos is not very well organized, so my next task will be trying to
> get that together. There are lots of interesting things in Deimos now (and some
> of them I don't even know what they are), but what we're lacking is overall
> organization, a build script, a "ready-to-go" downloadable library, proper
> doxygen documentation, and so on. It's a bit irritating, so I guess now is the
> time to deal with that. In the meantime, you can download the etc.unicode source
> files and documentation and build-it-yourself. (But be patient. There are A LOT
> of files to compile).
> 
> Arcane Jill
> 
> 

Arcane Jill wrote:
> Despite this space saving, the functions should still be pretty fast. The code
> for that uppercasing function consists of two if tests, a shift, a switch
> statement with seven cases, and a table lookup. And nothing else.

Hmmm. Why do you store each page separately with a manual switch for choosing the right one? A second lookup table should be a lot faster.

You could also save some more cycles if you add a single page that contains only 0 values instead of returning a null-pointer. That way you do not need to check for null every time you read a value.

But these are just minor points. This is a great piece of work.

Hauke

In article <cbnbdl$182e$1@digitaldaemon.com>, Walter says...
>
>Cool! Is this a supplement or a replacement for Hauke's earlier work?

Both really. etc.unicode is a very different beast from unichar. Hauke's unichar is very easy to use - there's just one source file. You stick that source file in your project and you're done. With etc.unicode it is (for now) more complicated, as there are many, many source files, and, what with Deimos being slightly disorganized at present, it may be a while before we get a build script together. Deimos will work like Phobos - you download a lib and link against it. But we're not that organized yet. Getting Deimos organized now has quite a high priority for me (more even that writing code, and that's saying something).

It's a replacement for PART of Hauke's work. Hauke's utype module will always be
necessary if you want a drop-in replacement for ctype. We should keep that
forever. I don't know how isprint() and isgraph() are implemented in utype right
now, but they could in any case be implemented in terms of etc.unicode if
needed. (isgraph() == isGraphemeBase() || isGraphemeExtend()), etc.

etc.unicode does overlap the functionality of unichar though. That's because etc.unicode is written by robot, and it was easier to get the robot to write the lot rather than just some of it. I need to make the codebuilder robot public - or at least available to Hauke - because he may want to tweak it in places.

Arcane Jill

In article <cbneog$1cu3$1@digitaldaemon.com>, Hauke Duden says...
>
>Arcane Jill wrote:
>> Despite this space saving, the functions should still be pretty fast. The code for that uppercasing function consists of two if tests, a shift, a switch statement with seven cases, and a table lookup. And nothing else.
>
>Hmmm. Why do you store each page separately with a manual switch for choosing the right one? A second lookup table should be a lot faster.
>
>You could also save some more cycles if you add a single page that contains only 0 values instead of returning a null-pointer. That way you do not need to check for null every time you read a value.


The old space/speed tradeoff. You can probably tweak this, once I make the codebuilder program public. There are various parameters which control decisions the robot makes, and right now those parameters are just constants. But we COULD change that so that more popular lookup get biased in favor of speed, while less popular lookups get biased in favor of minimal space. In the current configuration, the robot decides that a big table full of zeroes is a waste of space compared with a test for null, and that a switch statement is acceptable so long as there are fewer than sixteen cases. But all these things are ultimately tweakable if we later decide to tweak them. If we do that, the robot will simply write different code (i.e. faster but bigger).

Personally, I think that the choices currently made are quite reasonable for most properties. There may be a case for speeding up uppercasing and a few others, but you still have to think in terms of how much RAM that would consume at runtime. Right now it's 5K for uppercasing, and another 5K for lowercasing. Unicode contains a *lot* of data, and I'm hesitant to give speed too high a priority here, for fear of everything getting huge.

Arcane Jill

Arcane Jill wrote:
> In article <cbneog$1cu3$1@digitaldaemon.com>, Hauke Duden says...
> 
>>Arcane Jill wrote:
>>
>>>Despite this space saving, the functions should still be pretty fast. The code
>>>for that uppercasing function consists of two if tests, a shift, a switch
>>>statement with seven cases, and a table lookup. And nothing else.
>>
>>Hmmm. Why do you store each page separately with a manual switch for choosing the right one? A second lookup table should be a lot faster.
>>
>>You could also save some more cycles if you add a single page that contains only 0 values instead of returning a null-pointer. That way you do not need to check for null every time you read a value.
> 
> 
> 
> The old space/speed tradeoff. You can probably tweak this, once I make the
> codebuilder program public. There are various parameters which control decisions
> the robot makes, and right now those parameters are just constants. But we COULD
> change that so that more popular lookup get biased in favor of speed, while less
> popular lookups get biased in favor of minimal space. In the current
> configuration, the robot decides that a big table full of zeroes is a waste of
> space compared with a test for null, and that a switch statement is acceptable
> so long as there are fewer than sixteen cases. But all these things are
> ultimately tweakable if we later decide to tweak them. If we do that, the robot
> will simply write different code (i.e. faster but bigger).

Not necessarily bigger. If you add RLE compression it can even get smaller than what you have now.

I'd love to take a look at the "robot" code. I have some things in mind that might improve on both speed and size. I'd like to see how easy it would be to integrate them into your current system.


> Personally, I think that the choices currently made are quite reasonable for
> most properties. There may be a case for speeding up uppercasing and a few
> others, but you still have to think in terms of how much RAM that would consume
> at runtime. Right now it's 5K for uppercasing, and another 5K for lowercasing.
> Unicode contains a *lot* of data, and I'm hesitant to give speed too high a
> priority here, for fear of everything getting huge.

We're on the same page here. Both sides need to be optimized but you have to find a good balance.


Hauke

In article <cbosl4$f9d$1@digitaldaemon.com>, Hauke Duden says...

>Not necessarily bigger. If you add RLE compression it can even get smaller than what you have now.

You mentioned that before, but I'm not sure I agree. RLE is pretty much the /only/ one of your ideas that I didn't go with. You see, I take the view that hard disk space is plentiful, but RAM is not. With that perspective, compressing on disk, but decompressing into RAM, is /not/ a good thing to do. You might as well load it into RAM in the uncompressed state in the first place.



>I'd love to take a look at the "robot" code. I have some things in mind that might improve on both speed and size. I'd like to see how easy it would be to integrate them into your current system.

I thought you might. Rest assured, you will be the /first/ person to get write access. I'll probably need to start a new project for it thought. The codebuilder itself doesn't REALLY belong in Deimos, as it's not general purpose.



>We're on the same page here. Both sides need to be optimized but you have to find a good balance.

The codebuilder is a good way to get that balance. Change a few constants, run it again and new source gets written reflecting the new balance. But fine tuning it is probably more your area of expertise. You seem to know more about this sort of stuff than I, anyway.

Jill

Arcane Jill wrote:
> In article <cbosl4$f9d$1@digitaldaemon.com>, Hauke Duden says...
> 
> 
>>Not necessarily bigger. If you add RLE compression it can even get smaller than what you have now.
> 
> 
> You mentioned that before, but I'm not sure I agree. RLE is pretty much the
> /only/ one of your ideas that I didn't go with. You see, I take the view that
> hard disk space is plentiful, but RAM is not. With that perspective, compressing
> on disk, but decompressing into RAM, is /not/ a good thing to do. You might as
> well load it into RAM in the uncompressed state in the first place.

Heh. Sorry if I seem like I want to push my ideas onto you. I usually write these messages in a hurry and I'm often not sure if I have mentioned something before ;)

Regarding the size problem: for me the trade-off is not so much disk space against RAM usage but executable size against RAM usage. My concern is that if the executables get too big then people might not want to use the unicode functions for some applications (and fall back to ASCII instead). For example, good Setup software adds as little overhead as possible to the installed data. If all the Unicode stuff together amounts to 100K then that may already be too much.

You should also keep in mind that the executable is held in RAM as well, so increasing executable size to save RAM does not always give you an advantage.

Please also let me emphasize that I'm not advocating holding completely uncompressed tables in RAM. On the contrary: I think the layout you currently have is good for the uncompressed version.
What I mean is not storing this data directly in the executable, but storing an RLE compressed version and unpacking it into the current form at runtime. The RLE'ed version should be quite a bit smaller (it reduces the mapping data in unichar to about 1/4th). So the increase in RAM usage would be around 125% of what you have now (assuming that the other data packs similarly well - the 25% increase comes from the second RLE compressed version of the data in the executable). But executable size goes down to 25%. I think that's worth it.

Also keep in mind that we're talking about kilobyte sizes here. 500 KB of RAM is not much nowadays (my estimate for an application that uses just about everything), but downloading 500 KB more from the internet is very noticable for modem users.

>>I'd love to take a look at the "robot" code. I have some things in mind that might improve on both speed and size. I'd like to see how easy it would be to integrate them into your current system.
> 
> 
> I thought you might. Rest assured, you will be the /first/ person to get write
> access. I'll probably need to start a new project for it thought. The
> codebuilder itself doesn't REALLY belong in Deimos, as it's not general purpose.

Take your time - I'm curious, but I don't have much free time to spend on this anyway. I can wait :).


Hauke

In article <cbpp7k$1pgi$1@digitaldaemon.com>, Hauke Duden says...

>You should also keep in mind that the executable is held in RAM as well,

As well as what?

The tables are directly contained in the RAM image of the executable. They are not duplicated or otherwise reconstructed. They are accessed in-place.



>so increasing executable size to save RAM does not always give you an advantage.

Curiously, you seem to be arguing in favor of my position. Had we used RLE decompression, THEN we'd have to worry about the "as well".

Jill