In depth 1, the resulting bits will always be 0.<br>
It's not a big problem because rgbMul is just a bitAnd operation at this depth.<br>
So a quick workaround would be to detect the case in BitBltSimulation
destDepth = 1 ifTrue: [^self bitAnd: sourceWord with: destinationWord].
That would also accelerate the Bit BLock Transfer operation, so it's a good hack.
But there is more. What we want is multiply ratios in interval [0,1].
dstRatio * srcRatio
Our implementation is scaled ratio (scaled by `1 << nBits - 1`):
src := (srcRatio * scale) rounded.
dst := (dstRatio * scale) rounded.
So what we want is:
((dst/scale) * (src/scale) * scale) rounded
that is:
(dst*src / (1<<nBits-1)) rounded
Unfortunately, that's the other grief with the current implementation used for rounding:
(dst+1)*(src+1) - 1 >> nBits
It only equals correctly rounded operation for depths 2 and 4.
For rounding we might use:
(((dst/scale) * (src/scale) + 0.5) * scale) truncated.
that is expressed with truncated division:
dst*src + (scale+1//2) // scale
So here is a nicer formulation for doing the job at any depth (including 5bits rgb channels for 16 bits depth) with correctly rounded division:
aux := src * dst + (1 << (nBits - 1)). "add mid-scale for rounding"
result := aux << (nBits - 1) + aux << (nBits -1). "divide by scale"
This is because instead of dividing by scale, we can multiply by shifted inverse (sort of double precision), then shift right.
(2 to: 32) allSatisfy: [:nBits | (1 << (nBits * 2) / (1 << nBits - 1)) rounded = (1 << nBits + 1)].
Multiplying by this inverse is easy and cheap:
x * (1 << nBits + 1) = (x << nBits + x).
And then applying the right shift `>> (2 * nBits)` is equivalent to:
x >> nBits + x >> nBits.
We must first add 0.5 (scaled), that is `src * dst + (1 << (nBits -1))` - our formulation of aux, and we're done.
We verify:
{
(0 to: 1<<20-1) allSatisfy: [:i | (1<<9+i)>>10+ (1<<9+i)>>10 = (i/1023) rounded].
(0 to: 1<<18-1) allSatisfy: [:i | (1<<8+i)>>9+ (1<<8+i)>>9 = (i/511) rounded].
(0 to: 1<<16-1) allSatisfy: [:i | (1<<7+i)>>8+ (1<<7+i)>>8 = (i/255) rounded].
(0 to: 1<<14-1) allSatisfy: [:i | (1<<6+i)>>7+ (1<<6+i)>>7 = (i/127) rounded].
(0 to: 1<<12-1) allSatisfy: [:i | (1<<5+i)>>6+ (1<<5+i)>>6 = (i/63) rounded].
(0 to: 1<<10-1) allSatisfy: [:i | (1<<4+i)>>5+ (1<<4+i)>>5 = (i/31) rounded].
(0 to: 1<<8-1) allSatisfy: [:i | (1<<3+i)>>4+ (1<<3+i)>>4 = (i/15) rounded].
(0 to: 1<<6-1) allSatisfy: [:i | (1<<2+i)>>3+ (1<<2+i)>>3 = (i/7) rounded].
(0 to: 1<<4-1) allSatisfy: [:i | (1<<1+i)>>2+ (1<<1+i)>>2 = (i/3) rounded].
} allSatisfy: #yourself.
The nice thing is that above down-scaling operation can be multiplexed.<b>
Suppose that we have p groups of 2*nBits `M` holding square-scale multiplication of each channel concatenated in a double-Word-Mul.
doubleWordMul = Mp .... M5 M3 M1
Note we arrange to have odd channels in low word, and even channels in high word.
We first form a `groupMask` on a word with (p+1)/2 groups of nBits alternating all one `i` and all zero `o`, `oioi...ioi`.<br>
channelMask := 1 << nBits - 1.
groupMask := 0.
0 to: wordBits // (2 * nBits) do: [:i |
groupMask = groupMask << (2 * nBits) + channelMask].
Where wordBits is the number of bits in a word (usually we want to operate on 32 bits words in BitBlt).
We form the `doubleGroupMask` on a double-word with p groups of 2*nBits `oi`:
doubleGroupMask := groupMask >> nBits.
doubleGroupMask := doubleGroupMask << wordBits + groupMask.
And we perform the division by scale:
doubleWordMul := (doubleWordMul >> nBits bitAnd: doubleGroupMask) + doubleWord >> nBits bitAnd: doubleGroupMask.
At this stage we obtain a double word containing scaled multiplicands interleaved with groups of nBits zeros:
o mp ... o m3 o m1
Now the final result can be obtained by shifting back:
doubleWordMul >> (wordBits - nBits) + (doubleWordMul bitAnd: groupMask)
The only problem remaining is how to obtain the squared-scale multiplicands. It would be easy to form the alternate even-odd channels for each src and dst operands:
doubleWordSrc := src >> nBits bitAnd: groupMask.
doubleWordSrc := doubleWordSrc << wordBits + (src bitAnd: groupMask).
doubleWordDst := dst >> nBits bitAnd: groupMask.
doubleWordDst := doubleWordDst << wordBits + (dst bitAnd: groupMask).
we now get `o sp ... o s3 o s1` and `0 dp ... o d3 o d1`, but we would now need a SIMD integer multiplication operating on groups of 2*nBits in parallel... We don't have that, at least in portable C code. So we still have to emulate it with a loop.
half := 1 << (nBits - 1).
shift := 0.
doubleWordMul := 0
0 to: nChannels - 1 do: [:i |
doubleWordMul := doubleWordMul + (((doubleWordSrc >> shift bitAnd: channelMask) * (doubleWordSrc >> shift bitAnd: channelMask) + half) << shift).
shift := shift + nBits + nBits].
We know that each operation cannot overflow on upper neighbour group of 2*nBits, because the maximum value is:
(1<<nBits-1) squared + (1 << (nBits-1)) = 1 << (2*nBits) - (2*(1<<nBits)) + (1 << (nBits-1)) - 1
< (1 << (2*nBits) - 1)
It remains the odd case of 16 bits depth, which has 3 groups of 5 bits and a leading zero.
I believe that above algorithm works without splitting in two half-words...
To be tested.
We have gathered the pieces for a correctly rounded almost-multiplexed rgbMul.<br>
Somehow have our cake and eat it too.
--
Reply to this email directly or view it on GitHub:
https://github.com/OpenSmalltalk/opensmalltalk-vm/issues/651
You are receiving this because you are subscribed to this thread.
Message ID: <OpenSmalltalk/opensmalltalk-vm/issues/651(a)github.com>
Hello,
My name is Pierre Misse-Chanabier.
I'm finishing my PhD in the RMOD team on testing Virtual Machines soon.
I wanted to share with you a project I did with Theo Rogliano on the
Pharo VM, which should be straightforward to use on the OpenSmalltalk-VM
as well.
Except for the UI, of course !
In a nutshell, Polyphemus [1] reifies OOPs in the memory to propose a
representation that is closer to the language level.
Therefore, it provides a layer that is easier to work with.
For example, if an OOP is pointing to a class, I can ask for its name,
inspect it as I would at the language level, or send message special to
a class that shouldn't work on a string OOP for example.
We have develop a few visualizations and basic tools for the Pharo VM.
Particularly, we have been able to fix error containing meta-errors and
memory corruptions.
You may have encounter a video of this at the Technological Innovation
award at ESUG 2022 [2].
We have also wrote a paper that will be published soon at VMIL 2022 [3].
I haven't checked in quite a long time, but I think that most (or all)
of the simulator features we use in Polyphemus are available in the
OpenSmalltal-VM as well.
I hope it'll be useful to someone else, or at least interesting to some
of you :)
Pierre
[1] Github Repository: https://github.com/hogoww/Polyphemus/
[2] Video Presentation for Esug Innovation award (I was unable to
present it myself): https://www.youtube.com/watch?v=zf3cCtNW830
[3] VMIL'22: Ease VM Level Tooling with Language Level Ordinary Object
Pointers https://hal.inria.fr/hal-03827632 (preprint)
Repairs FileDirectory>>#exists for long paths (> 260 characters) on Windows by well-defining an edge case in the Windows implementation of the FilePlugin primitiveDirectoryEntry, that is, to specify a single dot (.) as the file name. Documents the present limitations to syntactic sugar in long file paths in the platform code, the relevant plugin methods, and on the image side of Squeak Trunk.
An alternative consideration was to rewrite FileDirectory>>#exists to pass an empty string as file name to the primitive instead of modifying the VM, but strictly speaking, even this would have exploited an undefined behavior in the VM plugin, and an empty file name would be less idiomatic than a single dot.
For the original bug report, see: https://github.com/hpi-swa-teaching/Morphic-Testing-Framework/issues/13 Thanks to Marcel (mt) for his support!
Signed-off-by: Christoph Thiede <christoph.thiede(a)student.hpi.de>
---
Note that this mail contains both a git diff for the changes in the opensmalltalk-vm repository and a changeset for the changes in the Squeak Trunk so that they may be reviewed together. Any feedback on this formatting approach will be appreciated. Excited to receive your review!
platforms/win32/vm/sqWin32Directory.c | 29 +++++++++++++++++++++++++++
1 file changed, 29 insertions(+)
diff --git a/platforms/win32/vm/sqWin32Directory.c b/platforms/win32/vm/sqWin32Directory.c
index 2b3d090ec..0aa5c2108 100644
--- a/platforms/win32/vm/sqWin32Directory.c
+++ b/platforms/win32/vm/sqWin32Directory.c
@@ -196,6 +196,15 @@ sqInt dir_Lookup(char *pathString, sqInt pathLength, sqInt index,
/* Lookup the index-th entry of the directory with the given path, starting
at the root of the file system. Set the name, name length, creation date,
creation time, directory flag, and file size (if the entry is a file).
+
+ Note that, due to restrictions by the operating system, this method only
+ has limited support for paths longer than 260 characters. In the case of
+ longer paths, they must not contain syntactic sugar such as ".", "..", or
+ "a/b".* For more details, see:
+ https://learn.microsoft.com/en-us/windows/win32/fileio/naming-a-file#paths
+ *) Long paths are automatically converted into UNC paths, which only
+ support a subset of the normal path syntax.
+
Return:
0 if a entry is found at the given index
1 if the directory has fewer than index entries
@@ -354,6 +363,20 @@ sqInt dir_EntryLookup(char *pathString, sqInt pathLength, char* nameString, sqIn
/* Lookup a given file in a given named directory.
Set the name, name length, creation date,
creation time, directory flag, and file size (if the entry is a file).
+
+ Note that, due to restrictions by the operating system, this method only
+ has limited support for paths longer than 260 characters (for the full
+ path concatenated from the directory path, a backslash, and the file
+ name). In the case of longer paths, neither the path nor the file name
+ must contain syntactic sugar such as ".", "..", or "a/b".* However, this
+ method defines a single (!) convention for passing nameString as ".",
+ which is also supported for long paths. This convention is provided for
+ an efficient existence check of the directory (e.g.,
+ FileDirectory>>#exists). For more details, see:
+ https://learn.microsoft.com/en-us/windows/win32/fileio/naming-a-file#paths
+ *) Long paths are automatically converted into UNC paths, which only
+ support a subset of the normal path syntax.
+
Return:
0 if found (a file or directory 'nameString' exists in directory 'pathString')
1 if the directory has no such entry
@@ -416,6 +439,12 @@ sqInt dir_EntryLookup(char *pathString, sqInt pathLength, char* nameString, sqIn
fullPath=(char *)calloc(fullPathLength,sizeof(char));
memcpy(fullPath,pathString,pathLength);
if (pathString[pathLength-1] != '\\') fullPath[pathLength]='\\';
+ if (nameStringLength == 1 && nameString[0] == '.') {
+ /* special syntax: "." is the current directory. Trim it from the full
+ path to avoid generating a UNC path with an unresolved ".", which is
+ not supported there. See comment above. */
+ nameStringLength = 0;
+ }
memcpy(fullPath+fullPathLength-nameStringLength,nameString,nameStringLength);
/* convert the path name into a null-terminated C string */
--
2.37.3.windows.1
=============== Summary ===============
Change Set:Â Â Â Â Â Â Â Â noUNCPaths
Date:Â Â Â Â Â Â Â Â Â Â Â Â 30 November 2022
Author:Â Â Â Â Â Â Â Â Â Â Â Â Christoph Thiede
Documents the present limitations to syntactic sugar in long file paths in the relevant plugin methods and on the image side.
For the original bug report, see: https://github.com/hpi-swa-teaching/Morphic-Testing-Framework/issues/13 Thanks to Marcel (mt) for his support!
=============== Diff ===============
FileDirectory>>primLookupEntryIn:index: {private} · ct 11/29/2022 20:24 (changed)
primLookupEntryIn: fullPath index: index
    "Look up the index-th entry of the directory with the given fully-qualified path (i.e., starting from the root of the file hierarchy) and return an array containing:
    <name> <creationTime> <modificationTime> <dirFlag> <fileSize>
    The empty string enumerates the top-level files or drives. (For example, on Unix, the empty path enumerates the contents of '/'. On Macs and PCs, it enumerates the mounted volumes/drives.)
+ Â Â Â Â Note that in general, fullPath must not contain syntactic sugar for the current platform (e.g., '.' or '..', or on Windows, forward slashes instead of backslashes). These conventions are only fully supported on Unix platforms; on Windows, they are only supported for short non-UNC file paths containing max 260 characters. See the comment in the primitive implementation for more details.
    The creation and modification times are in seconds since the start of the Smalltalk time epoch. DirFlag is true if the entry is a directory. FileSize the file size in bytes or zero for directories. The primitive returns nil when index is past the end of the directory. It fails if the given path is bad."
    <primitive: 'primitiveDirectoryLookup' module: 'FilePlugin'>
    ^ #badDirectoryPath
FileDirectory>>primLookupEntryIn:name: {private} · ct 11/30/2022 15:38 (changed)
primLookupEntryIn: fullPath name: fName
-
    "Look up <fName> (a simple file name) in the directory identified by <fullPath>
    and return an array containing:
    <fName> <creationTime> <modificationTime> <dirFlag> <fileSize>
    On Unix, the empty path denotes '/'.
On Macs and PCs, it is the container of the system volumes.)
+ Â Â Â Â Note that in general, neither fullPath nor fName must contain syntactic sugar for the current platform (e.g., '.' or '..', or on Windows, forward slashes instead of backslashes). These conventions are only fully supported on Unix platforms; on Windows, they are only supported for short non-UNC file paths containing max 260 characters (for the full path concatenated from the directory path, a backslash, and the file name). As a single (!) exception, the file name may always be a single dot ('.'), which is supported for an efficient existence test of the directory path (e.g., FileDirectory>>#exists). See the comment in the primitive implementation for more details.
    The creation and modification times are in seconds since the start of the Smalltalk time epoch. DirFlag is true if the entry is a directory. FileSize the file size in bytes or zero for directories. The primitive returns nil when index is past the end of the directory. It fails if the given path is bad."
    <primitive: 'primitiveDirectoryEntry' module: 'FilePlugin'>
    ^ #primFailed        "to distinguish from nil"
FilePlugin>>primitiveDirectoryEntry {directory primitives} · ct 11/30/2022 15:13 (changed)
primitiveDirectoryEntry
    "Two arguments - directory path, and simple file name;
    returns an array (see primitiveDirectoryLookup) describing the file or directory,
    or nil if it does not exist.
+ Â Â Â Â
+ Â Â Â Â Note that in general, neither the directory path nor the file name must
+ Â Â Â Â contain syntactic sugar for the current platform (e.g., '.' or '..', or on
+ Â Â Â Â Windows, forward slashes instead of backslashes). These conventions are
+ Â Â Â Â only fully supported on Unix platforms; on Windows, they are only
+ Â Â Â Â supported for short non-UNC file paths containing max 260 characters (for
+ Â Â Â Â the full path concatenated from the directory path, a backslash, and the
+ Â Â Â Â file name). As a single (!) exception, the file name may always be a
+ Â Â Â Â single dot ('.'), which is supported for an efficient existence test of
+ Â Â Â Â the directory path (e.g., FileDirectory>>#exists). See the comment in
+ Â Â Â Â sqWin32Directory.c for more details.
+ Â Â Â Â
    Primitive fails if the outer path does not identify a readable directory.
    (This is a lookup-by-name variant of primitiveDirectoryLookup.)"
    | requestedName pathName pathNameIndex pathNameSize status entryName entryNameSize createDate modifiedDate dirFlag posixPermissions symlinkFlag fileSize okToList reqNameIndex reqNameSize |
   Â
    <var: 'entryName' declareC: 'char entryName[256]'>
    <var: 'pathNameIndex' type: #'char *'>
    <var: 'reqNameIndex' type: #'char *'>
    <var: 'fileSize' type: #squeakFileOffsetType>
    <export: true>
    requestedName := interpreterProxy stackValue: 0.
    pathName := interpreterProxy stackValue: 1.
    (interpreterProxy isBytes: pathName) ifFalse:
        [^interpreterProxy primitiveFail].
    "Outbound string parameters"
    pathNameIndex := interpreterProxy firstIndexableField: pathName.
    pathNameSize := interpreterProxy byteSizeOf: pathName.
    reqNameIndex := interpreterProxy firstIndexableField: requestedName.
    reqNameSize := interpreterProxy byteSizeOf: requestedName.
    self cCode: '' inSmalltalk:
        [entryName := ByteString new: 256.
        entryNameSize := createDate := modifiedDate := dirFlag := fileSize := posixPermissions := symlinkFlag := nil].
    "If the security plugin can be loaded, use it to check for permission.
    If not, assume it's ok"
    okToList := sCLPfn ~= 0
                    ifTrue: [self cCode: '((sqInt (*)(char *, sqInt))sCLPfn)(pathNameIndex, pathNameSize)' inSmalltalk: [true]]
                    ifFalse: [true].
    status := okToList
        ifTrue:
            [self dir_EntryLookup: pathNameIndex _: pathNameSize
                    _: reqNameIndex _: reqNameSize
                    _: entryName _: (self addressOf: entryNameSize put: [:v| entryNameSize := v])
                    _: (self addressOf: createDate put: [:v| createDate := v])
                    _: (self addressOf: modifiedDate put: [:v| modifiedDate := v])
                    _: (self addressOf: dirFlag put: [:v| dirFlag := v])
                    _: (self addressOf: fileSize put: [:v| fileSize := v])
                    _: (self addressOf: posixPermissions put: [:v| posixPermissions := v])
                    _: (self addressOf: symlinkFlag put: [:v| symlinkFlag := v])]
        ifFalse:
            [DirNoMoreEntries].
    interpreterProxy failed ifTrue:
        [^nil].
    status = DirNoMoreEntries ifTrue: "no entry; return nil"
        [interpreterProxy "pop pathName, index, rcvr"
            pop: 3 thenPush: interpreterProxy nilObject.
            ^nil].
    status = DirBadPath ifTrue:
        [^interpreterProxy primitiveFail]."bad path"
    interpreterProxy
        pop: 3    "pop pathName, index, rcvr"
        thenPush:
            (self
                cppIf: PharoVM
                ifTrue:
                    [self
                        makeDirEntryName: entryName
                        size: entryNameSize
                        createDate: createDate
                        modDate: modifiedDate
                        isDir: dirFlag
                        fileSize: fileSize
                        posixPermissions: posixPermissions
                        isSymlink: symlinkFlag]
                ifFalse:
                    [self
                        makeDirEntryName: entryName
                        size: entryNameSize
                        createDate: createDate
                        modDate: modifiedDate
                        isDir: dirFlag
                        fileSize: fileSize])
FilePlugin>>primitiveDirectoryLookup {directory primitives} · ct 11/30/2022 15:00 (changed)
primitiveDirectoryLookup
+ Â Â Â Â "Two arguments - directory path, and an index to an item; returns an array (see primitiveDirectoryLookup) describing the file or directory, or nil if it does not exist.
+ Â Â Â Â
+ Â Â Â Â Note that in general, the directory path must not contain syntactic sugar for the current platform (e.g., '.' or '..', or on Windows, forward slashes instead of backslashes). These conventions are only fully supported on Unix platforms; on Windows, they are only supported for short non-UNC file paths containing max 260 characters. See the comment in sqWin32Directory.c for more details.
+ Â Â Â Â
+ Â Â Â Â Primitive fails if the outer path does not identify a readable directory. (For a lookup-by-name variant, see primitiveDirectoryEntry.)"
    | index pathName pathNameIndex pathNameSize status entryName entryNameSize createDate modifiedDate dirFlag symlinkFlag posixPermissions fileSize okToList |
   Â
    <var: 'entryName' declareC: 'char entryName[256]'>
    <var: 'pathNameIndex' type: #'char *'>
    <var: 'fileSize' type: #squeakFileOffsetType>
    <export: true>
    index := interpreterProxy stackIntegerValue: 0.
    pathName := interpreterProxy stackValue: 1.
    (interpreterProxy isBytes: pathName)
        ifFalse: [^interpreterProxy primitiveFail].
    pathNameIndex := interpreterProxy firstIndexableField: pathName.
    pathNameSize := interpreterProxy byteSizeOf: pathName.
    self cCode: '' inSmalltalk:
        [entryName := ByteString new: 256.
        entryNameSize := createDate := modifiedDate := dirFlag := fileSize := posixPermissions := symlinkFlag := nil].
    "If the security plugin can be loaded, use it to check for permission.
    If not, assume it's ok"
    okToList := sCLPfn ~= 0
                    ifTrue: [self cCode: '((sqInt (*)(char *, sqInt))sCLPfn)(pathNameIndex, pathNameSize)' inSmalltalk: [true]]
                    ifFalse: [true].
    status := okToList
        ifTrue:
            [self dir_Lookup: pathNameIndex _: pathNameSize
                    _: index
                    _: entryName _: (self addressOf: entryNameSize put: [:v| entryNameSize := v])
                    _: (self addressOf: createDate put: [:v| createDate := v])
                    _: (self addressOf: modifiedDate put: [:v| modifiedDate := v])
                    _: (self addressOf: dirFlag put: [:v| dirFlag := v])
                    _: (self addressOf: fileSize put: [:v| fileSize := v])
                    _: (self addressOf: posixPermissions put: [:v| posixPermissions := v])
                    _: (self addressOf: symlinkFlag put: [:v| symlinkFlag := v])]
        ifFalse: [DirNoMoreEntries].
    interpreterProxy failed ifTrue:
        [^nil].
    status = DirNoMoreEntries ifTrue: "no more entries; return nil"
        [interpreterProxy "pop pathName, index, rcvr"
            pop: 3 thenPush: interpreterProxy nilObject.
        ^nil].
    status = DirBadPath ifTrue:
        [^interpreterProxy primitiveFail]."bad path"
    interpreterProxy
        pop: 3    "pop pathName, index, rcvr"
        thenPush:
            (self
                cppIf: PharoVM
                ifTrue:
                    [self
                        makeDirEntryName: entryName
                        size: entryNameSize
                        createDate: createDate
                        modDate: modifiedDate
                        isDir: dirFlag
                        fileSize: fileSize
                        posixPermissions: posixPermissions
                        isSymlink: symlinkFlag]
                ifFalse:
                    [self
                        makeDirEntryName: entryName
                        size: entryNameSize
                        createDate: createDate
                        modDate: modifiedDate
                        isDir: dirFlag
                        fileSize: fileSize])
---
Sent from Squeak Inbox Talk
["noUNCPaths.3.cs"]