suppose the data were generated by a csprng with 256 bits of state. then in fact there are just slightly more than 256 bits of entropy there (prng state plus the length of the generated file). only, you'd have a snail's chance in hell of actually finding that seed
If he really wanted to make sure he kept the money, he could just use a hardware RNG. I don’t know how common they were in 2001 but you could probably even generate some practically unpredictable random numbers using radio noise.
i suppose you can probably do anything with dependent types, but i'm not sure this is a useful perspective. i commend you to read my comments on the red website https://lobste.rs/s/xkcrvn/
(i do think it is a valid question whether abstract interpretation is a good idea)
they are talking about treating ocr as lossy. i wonder about making a lossless compression algorithm for text scans based on an ocr; in effect, use the ocr to predict which text will show up and how, and then encode the pixel-level differences on top of that
depends how you define causality. if you consider the execution of one operation to cause the execution of the next operation in program order, then causality was already broken by simple reordering. if it's a read-write dependency, on the other hand, then it won't be broken (because cpus respect control dependencies); hence, you cannot, for example, replicate oota this way. what's broken is specifically read-read data dependencies. and only on weakly-ordered architectures; it won't do anything on x86
> I've never heard anything about these sorts of graph algorithms being possible with good asymptotics in an array style
yeah—idk graph algos really, but have heard parallelising combinatorial search in general (eg sat) is hard because forks and joins happen heterogeneously and erratically. this 2001 vintage has a bunch of completely sequential graph colouring algorithms in j https://dl.acm.org/doi/pdf/10.1145/570406.570416 (and j at least has sparse matrices!)
> Constant lifting within the compiler is pretty cool, I'll have to look into that.
hrm, it seems to refer to 2 things: 1) constants allocated in a special space; 2) interning. 2 is obviously worthwhile; 1 i would guess is related to memory being weird on the gpu?
It's still just doing exactly what shaders do, which is crazy.
Explain to me exactly why, other than 'I guess someone already implemented some kind of basic version of it' that you would have to have custom CPU code rendering glyphs instead of a shader rendering SDF's like literally everyone does with shaders already?
It's not a good solution. It's a bad, easy solution.
We have a solution for running arbitrary GPU accelerated graphics instructions; it has a cross platform version with webGPU.
This font thing... looks a lot like 'not invented here' syndrome to me, as an uninvolved spectator.
Why would you chose or want not to use GPU acceleration to render your glyphs?
What 'arbitrary code' does a font need to do that couldn't be implemented in a shader?
Maybe the horse has already bolted, yes, I understand programmable fonts already exist.. but geez, its incomprehensible to me, at least from what I can see.
> Explain to me exactly why, other than 'I guess someone already implemented some kind of basic version of it' that you would have to have custom CPU code rendering glyphs instead of a shader rendering SDF's like literally everyone does with shaders already?
Shaping is different compared to rendering glyphs themselves. SDF renderers (and other GPU text renderers like Slug) still do shaping on the CPU, not in shaders. Maybe some experiments have been done in this area, but I doubt anyone shapes text directly in the GPU in practice.
Think of it like a function that takes text as input, and returns positions as output. Shaders don't really know anything about text. Sure you could probably implement it if you wanted to, but why would you? I think it would add complexity for no benefit (not even performance).
Very interesting. Honestly I don't know much about hinting, but I suspect the whole shaping stack that Slug supports:
> kerning, ligature replacement, combining diacritical mark placement, and character composition. Slug also supports a number of OpenType features that include stylistic alternates, small caps, oldstyle figures, subscripts, superscripts, case-sensitive punctuation, and fractions.
> CPU code rendering glyphs instead of a shader rendering SDF's
1) Because SDFs suck badly (and don't cover the whole field) when you want to render sharp text. SDFs are fine when used in a game where everything is mapped to textures and is in motion at weird angles. SDFs are not fine in a static document which is rendered precisely in 2D.
2) Because GPUs handle "conditional" anything like crap. GPUs can apply a zillion computations as long as those computations apply to everything. The moment you want some of those computations to only apply to these things GPUs fall over in a heap. Every "if" statement wipes out half your throughput.
3) Because "text rendering" is multiple problems all smashed together. Text rendering is vector graphics--taking outlines and rendering them to a pixmap. Text rendering is shaping--taking text and a font and generating outlines. Text rendering is interactive--taking text and putting a selection or caret on it. None of these things parallelize well except maybe vector rendering.
I feel like, looking at the complexity of the programs that can be implemented in shaders (eg. https://dev.epicgames.com/documentation/en-us/unreal-engine/...) that it's unreasonable, bordering on disingenuous to suggest that the GPU pipeline is not capable enough to handle those workloads, or produce pixel perfect outputs.
Be really specific.
What exactly is it that you can't do in a shader, that you can do in a CPU based sandbox, better and faster?
(There are things, sure, like IO, networking, shared memory but I'm struggling to see why you would want any of them in this context)
I'll accept the answer, 'well, maybe you want to render fonts on a toaster with no GPU'; sure... but that having a GPU isn't good enough for you, yeah... nah. I'm not buying that).
Vector graphics are really hard to do on a GPU in an efficient manner. The way the data is stored as individual curve segments makes it difficult to parallelize the coverage problem, it's equivalent to a global parse; the best approaches all do some form of parsing of curve data on the CPU, either rasterizing fully on the GPU, or putting it in a structure the GPU can chew on.
But again, this has nothing to do with HarfBuzz or wasm.
what exactly do you mean by 'global parse'? it's very usual, i think, when operating on data stored in files, to parse them into in-memory structures before operating on them? but it feels like you are talking about something specific to vector rendering
slug builds acceleration structures ahead of time. the structures are overfit to the algorithm in a way that ttf should be but which is economical for video games. that doesn't seem like an interesting concern and nothing about it is specific to the gpu
I'm referring to needing to traverse all path segments to determine the winding order for an individual pixel. You can't solve this problem locally, you need global knowledge. The easiest way to do this is to build an acceleration structure to contain the global knowledge (what Slug does), but you can also propagate the global knowledge across (Hoppe ravg does this).
It's more about the nature of the problem, not that you can't do it in shaders. After all, I think you can do pretty much anything in shaders if you try hard enough.
Even if you already have a GPU renderer for glyphs and any other vector data, you still want to know where to actually position the glyphs. And since this is highly dependent on the text itself and your application state (that lies on the CPU), it would actually be pretty difficult to do it directly on the GPU. The shader that you would want should emit positions, but the code to do that won't be easily ported to the GPU. Working with text is not really what shaders are meant for.
It has nothing to do with shaders? Despite the name, shaping is not the same thing as a shader, shaping selects and places individual glyphs given a collection of code points.
No part of the rasterizer or renderer is configurable here. As mentioned above, the rasterizer is already programmable with up to two different bespoke stack bytecode languages, but that has nothing to do with shaping through wasm.
While this presentation is extremely interesting, it would have been far more useful if you would have exported this view into a downloadable PDF file, instead of giving access to just this ephemeral preview.
i don't think that's right. it's just 1/t. after all, after t time, one task must have made progress; since there are t tasks, the probability that i'm the task that made progress is just 1/t
the primary point of confusion, i think, is that getting interrupted does not mean that you are necessarily going to lose the cas
i am not cheating; you are cheating by trying to do integer arithmetic instead of float arithmetic. in particular: 99 * progress is a (potentially big) integer; then the quotient, from my understanding of python, is equal to the mathematical quantity rn(99 * progress / total), which is not trivial to compute. (although cpython does tend to do a particularly bad job of this sort of thing.) (compare with c or with my version of the python, where it would be rn(rn(99 * progress) / rn(total)), rounding twice, which is very easy to compute. i'm not saying the c semantics is better, mind.) when you scale up by 10x, the numerator is <1/2 'ulp' away from the denominator, and so the quotient rounds up to 99 exactly; there is still double rounding (would have been triple rounding in c and my python), because we got rn(rn(99 * progress / total) + 0.5) where what we wanted was rn(99 * progress / total + 0.5) (which is mathematically always the correct result)
i agree it is not common to have so many steps. but if i were providing a routine that was intended to be robust where others were not, i would try to be comprehensive. and i would not try to do int math with floats unless i could show it to be robust (i have sketched such a stunt! https://gist.github.com/moon-chilled/60bd2ba687dc197d93a9d22...). the integer routine is simpler and more honest anyway, and it is obvious that it works uniformly for the entire range
note also that, with x floating, the python expressions 10 * x and 10 * x - 1 are equivalent, meaning the error is on input to the percent function. (if we set progress to 10 * x - 8, the immediately preceding fp number, we do get 99, but there is no deep reason for this, and it differs for different values of 10.)
> if your username is named after the band, good taste :)
my username comes from a book: the neverending story. i am more using the german version of the name these days but i do not feel like making a new account on this godforesaken website
you may find my improved table design of interest, which avoids the need for mirroring: https://outerproduct.net/trivial/2022-10-06_hash.html