1 Apr
2022
1 Apr
'22
3:59 p.m.
The recent discussion about Research choosing BSD's paging over
Reiser-London's brought to mind a stunning program by Reiser that
Research did adopt.
A critical primitive in the Blit terminal was bitblt (block transfer
of a rectangular area). It was used ubiquitously, for example to
refresh data when window-stacking changed, to move data within a
window, or to pop up a menu.. The display memory was word-oriented, so
bitblt was fraught with niggling details about bit alignment and
overlap of source and destination. A general bitblt subroutine was a
rats' nest of conditionals--grossly inefficient for important special
cases like scrolling.
Bitblt got refined (i.e. elaborated) several times before Reiser did
away with it entirely. Instead he wrote a just-in-time generator of
optimal code. Thousands of distinct variants, which varied in size
from 16 to 72 bytes, could be produced by the same 400 lines of
assembler code.
Doug
1 Apr
1 Apr
5:15 p.m.
On Apr 1, 2022, at 8:59 AM, Douglas McIlroy
<douglas.mcilroy(a)dartmouth.edu> wrote:
The recent discussion about Research choosing BSD's paging over
Reiser-London's brought to mind a stunning program by Reiser that
Research did adopt.
A critical primitive in the Blit terminal was bitblt (block transfer
of a rectangular area). It was used ubiquitously, for example to
refresh data when window-stacking changed, to move data within a
window, or to pop up a menu.. The display memory was word-oriented, so
bitblt was fraught with niggling details about bit alignment and
overlap of source and destination. A general bitblt subroutine was a
rats' nest of conditionals--grossly inefficient for important special
cases like scrolling.
Bitblt got refined (i.e. elaborated) several times before Reiser did
away with it entirely. Instead he wrote a just-in-time generator of
optimal code. Thousands of distinct variants, which varied in size
from 16 to 72 bytes, could be produced by the same 400 lines of
assembler code.
Doug
Does this exist for the rest of us to study?
David
5:26 p.m.
David Barto writes:
It's not insanely complicated by modern standards. Without any knowledge
of other work, I did the same thing for a 68020 based graphics system where
the JIT code went into the I-cache and was amazingly fast for its day.
If I remember correctly, things started with an outer-loop test to see
if there were overlapping regions to determine whether to go forward
to backwards to avoid having the destination trash the source.
Then, there was an inner loop test for whether or not the left edge
was on a word boundary, the right edge was on a word boundary, or
whether or not both edges were inside of the same word. Depending
on the results the generated inner loop code had left edge handling,
non-edge handling, and right edge handling code.
Finally, code was generated plugging in whatever was needed for the
op-code.
Maybe this is just a semantic nit, but to me this is just a better
implementation of bitblt, not doing away with it.
Jon
On Apr 1, 2022, at 8:59 AM, Douglas McIlroy
<douglas.mcilroy(a)dartmouth.edu> wrote:
The recent discussion about Research choosing BSD's paging over
Reiser-London's brought to mind a stunning program by Reiser that
Research did adopt.
A critical primitive in the Blit terminal was bitblt (block transfer
of a rectangular area). It was used ubiquitously, for example to
refresh data when window-stacking changed, to move data within a
window, or to pop up a menu.. The display memory was word-oriented, so
bitblt was fraught with niggling details about bit alignment and
overlap of source and destination. A general bitblt subroutine was a
rats' nest of conditionals--grossly inefficient for important special
cases like scrolling.
Bitblt got refined (i.e. elaborated) several times before Reiser did
away with it entirely. Instead he wrote a just-in-time generator of
optimal code. Thousands of distinct variants, which varied in size
from 16 to 72 bytes, could be produced by the same 400 lines of
assembler code.
Doug
Does this exist for the rest of us to study?
David 
7:41 p.m.
Jon Steinhart wrote in
<202204011726.231HQFm03349496(a)darkstar.fourwinds.com>om>:
|David Barto writes:
|>> On Apr 1, 2022, at 8:59 AM, Douglas McIlroy <douglas.mcilroy(a)dartmouth.e\
|>> du> wrote:
|>> The recent discussion about Research choosing BSD's paging over
|>> Reiser-London's brought to mind a stunning program by Reiser that
|>> Research did adopt.
|>>
|>> A critical primitive in the Blit terminal was bitblt (block transfer
|>> of a rectangular area). It was used ubiquitously, for example to
...
|>> Bitblt got refined (i.e. elaborated) several times before Reiser did
|>> away with it entirely. Instead he wrote a just-in-time generator of
|>> optimal code. Thousands of distinct variants, which varied in size
|>> from 16 to 72 bytes, could be produced by the same 400 lines of
|>> assembler code.
...
|> Does this exist for the rest of us to study?
...
|It's not insanely complicated by modern standards. Without any knowledge
|of other work, I did the same thing for a 68020 based graphics system where
|the JIT code went into the I-cache and was amazingly fast for its day.
|
|If I remember correctly, things started with an outer-loop test to see
|if there were overlapping regions to determine whether to go forward
|to backwards to avoid having the destination trash the source.
...
Only to add that "modern standard" C libraries define
"overlapping" by means of exclusivity, meaning that memcpy(x,
&x[1], 1) is an invalid overlapping that requires memmove() to be
used.
|#?132(0.02 1/76)|alp-2022:tmp$ cat t.c
|#include <string.h>
|void doit(char *cp);
|int main(void){
| char buf[3] = {'1', '2', '\0'};
| doit(buf);
| return buf[0];
|}
|void doit(char *cp){
| memcpy(cp, &cp[1], 2);
|}
|#?0(0.02 1/76)|alp-2022:tmp$ gcc -D_FORTIFY_SOURCE=2 -O -o zt t.c
|#?0(0.02 1/76)|alp-2022:tmp$ ./zt
|Illegal instruction
|#?132(0.02 1/76)|alp-2022:tmp$ gcc --version
|gcc (Alpine 11.2.1_git20220219) 11.2.1 20220219
|Copyright (C) 2021 Free Software Foundation, Inc.
|This is free software; see the source for copying conditions. There is NO
|warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
|
|#?0(0.02 1/76)|alp-2022:tmp$
Your mileage will vary though.
--steffen
|
|Der Kragenbaer, The moon bear,
|der holt sich munter he cheerfully and one by one
|einen nach dem anderen runter wa.ks himself off
|(By Robert Gernhardt)
9:31 p.m.
And yes, this _was_ bitblt, its apotheosis, not its elimination.
-rbo
On Sat, Apr 2, 2022 at 8:29 AM Rob Pike <robpike(a)gmail.com> wrote:
A copy of our paper is at https://9p.io/cm/cs/doc/87/archtr.ps.gz
-rob
9:43 p.m.
Steffen Nurpmeso writes:
Jon Steinhart wrote in
<202204011726.231HQFm03349496(a)darkstar.fourwinds.com>om>:
|David Barto writes:
|>> On Apr 1, 2022, at 8:59 AM, Douglas McIlroy <douglas.mcilroy(a)dartmouth.e\
|>> du> wrote:
|>> The recent discussion about Research choosing BSD's paging over
|>> Reiser-London's brought to mind a stunning program by Reiser that
|>> Research did adopt.
|>>
|>> A critical primitive in the Blit terminal was bitblt (block transfer
|>> of a rectangular area). It was used ubiquitously, for example to
...
|>> Bitblt got refined (i.e. elaborated) several times before Reiser did
|>> away with it entirely. Instead he wrote a just-in-time generator of
|>> optimal code. Thousands of distinct variants, which varied in size
|>> from 16 to 72 bytes, could be produced by the same 400 lines of
|>> assembler code.
...
|> Does this exist for the rest of us to study?
...
|It's not insanely complicated by modern standards. Without any knowledge
|of other work, I did the same thing for a 68020 based graphics system where
|the JIT code went into the I-cache and was amazingly fast for its day.
|
|If I remember correctly, things started with an outer-loop test to see
|if there were overlapping regions to determine whether to go forward
|to backwards to avoid having the destination trash the source.
...
Only to add that "modern standard" C libraries define
"overlapping" by means of exclusivity, meaning that memcpy(x,
&x[1], 1) is an invalid overlapping that requires memmove() to be
used.
Uh, yeah, but not relevant at least to the code I did which was written
in C but generated machine code, not calls to library functions.
749
days inactive
749
days old
6 comments
5 participants
participants (5)
-
David Barto -
Douglas McIlroy -
Jon Steinhart -
Rob Pike -
Steffen Nurpmeso