section 3.8.1.1 should have pseudocode

[mcr]

The interpretation of the <== and <==> is not clear.
There is clearly a IF/THEN implied, but it is not clear how to code this.

S_(i + 1, C_(i)) = zero_state_(S_(i, C_(i))) AND
l_(i) = L_(i) AND
t_(i) = R_(i) - r_(i) <==
(b_(i) = 0 <==>
L_(i) < R_(i) - r_(i))

Can you explain how this is meant to be read?  Maybe it’s just me, and maybe after you explain it I’ll whack myself on the head and say, “Doh!”

MAYBE:

 IF            (b_(i) =  0                          AND
                L_(i) <  R_(i) - r_(i))
THEN
   S_(i + 1, C_(i)) =  zero_state_(S_(i, C_(i))) ;
          l_(i) =  L_(i)                     ;
          t_(i) =  R_(i) - r_(i)              

[mcr]

@dericed

[michaelni]

IIRC the ==> <==> is not intended to be pseudocode. That is its not a "if" in code but rather a mathematical definition of the stream

[michaelni]

b_(i) = 0 implies L_(i) < R_(i) - r_(i)
L_(i) < R_(i) - r_(i) implies b_(i) = 0
b_(i) = 0 implies S_(i + 1, C_(i)) = zero_state_(S_(i, C_(i))) AND l_(i) = L_(i) AND t_(i) = R_(i) - r_(i)

in words IIRC

1. means a 0 symbol at position i implies a specific relation of the range coder state when at that position
2. means that specific relation of the range coder state when at position i implies that theres a 0 symbol
3. means that a 0 symbol at position i implies how the state transition for the i+1 pos

So these things should define both the decoding and encoding

[mcr]

okay, so this is an attempt do a bijection of the mapping to/from code state and bitstream?
Is there a precedence between <== and <==>? Maybe that's what confuses me most.

[michaelni]

A <== B <==> C is meant as
A <== B, B <==> C
which could also be written as
A <== (B <==> C)
which would make <==> have higher precedence

[dwbuiten]

What's worth noting is that this is the only bit of the spec that uses a mathematical definition like this (contrast it to the golomb-rice coding part of the spec).

When I implemented go-ffv1 I essentially ignored this part of the spec entirely, and had to use the original paper cited, and a bit of wikipedia. (I mentioned as much here: https://youtu.be/4HB7v7dItWE / https://mediaarea.net/Events/2019-12-05_NoTimeToWait4/13.%20Derek%20Buitenhuis%20-%20I%20Wrote%20an%20FFV1%20decoder%20in%20Go%20for%20Fun,%20What%20I%20learned%20going%20from%20Spec%20to%20Implementation/derek_nttw4_ffv1.pdf)

[JeromeMartinez]

@dwbuiten would you mind to suggest a patch to the spec about that for having all in the spec?
I am working on all the other issues of the review but this one seems too big for my poor math skills.

[dwbuiten]

I can devise a patch using pseudocode, but I'd like to hear @michaelni's opinion first.

[michaelni]

I find the mathematical definition quite elegant but it clearly is not working for people. So adding pseudocode for the get/put is the logic solution. Iam in favor to add such pseudocode in addition to the mathematical stuff

[JeromeMartinez]

So adding pseudocode for the get/put

As the spec is, as most (all?) specs, focused on decoding, I suggest to have the pseudocode for the "get" part only, in addition of the mathematical definition focused on the "put" part we already have, it may be a good balance between not enough and too much.

[michaelni]

As the spec is, as most (all?) specs, focused on decoding, I suggest to have the pseudocode for the "get" part only, in addition of the mathematical definition focused on the "put" part we already have, it may be a good balance between not enough and too much.

I agree

[dwbuiten]

Can this issue be closed now that there is pseudocode?

[dericed]

I suggest leaving this issue open as there's active discussion in Barry's DISCUSS and his recent comments.

Barry notes that the formulae would be more readable with more definitions to each component variable of the formulae. As Barry suggested I moved the variables from a narrative to definition list in https://github.com/FFmpeg/FFV1/pull/255/files, but I need input on adding the other missing variables.

My draft is:

L_(i) is the Low value of the Range
l_(i) is a temporary storage variable used in assigning values to L_(i)
R_(i) is the Range value
r_(i) is a temporary storage variable used in assigning values to R_(i)
t_(i) is a temporary storage variable used in assigning values to R_(i)
S_(x, i) is the ‘x, 1’-th State

but am I understanding this values correctly? @michaelni @dwbuiten

I think it would be helpful too to make the cross-references of Table 4 more specific by referencing the Figure of the formula rather than the full section.

Currently, we have:

Symbol	Definition
sg	Golomb Rice coded signed scalar Symbol coded with the method described in Section 3.8.2
br	Range coded Boolean (1-bit) Symbol with the method described in Section 3.8.1.1
ur	Range coded unsigned scalar Symbol coded with the method described in Section 3.8.1.2
sr	Range coded signed scalar Symbol coded with the method described in Section 3.8.1.2
sd	Sample difference Symbol coded with the method described in Section 3.8

Can these cross-references be more precise?

[dericed]

new nudge to @michaelni @dwbuiten on the questions of my last comment. Also for the formula of Section 3.8.1.1 would it make sense to group them in regards to the purpose they have?

[dwbuiten]

I agree with Barry that it's easier to parse as separate variables.

I'm not really sure how you intend to cross reference with Table 4, though? It's not really beneficial.

[JeromeMartinez]

It looks like this issue can be closed (#259 is merged).