support for seeking in stb_vorbis.c (payment)

[nothings]

Someone has currently declared their intent to pursue this. Historically, multiple people have looked at this and given up, though, so it may re-open.

stb_vorbis is this single-file C library for decoding ogg vorbis files: https://github.com/nothings/stb/blob/master/stb_vorbis.c

stb_vorbis doesn't have correctly-working seek functionality (e.g. being able to say 'start playback from sample number 31415926').

The payment for a correct implementation of this feature is 5000 USD. (It may go down again in a few months as the current amount is the sum of several individuals who may drop out if it doesn't get done soon enough.) Please let me know if you are working on it to make sure we don't end up with two people doing it at the same time, as only one correct implementation will be paid out.

Requirements:

• seeking must be sample-accurate
• reasonably efficient (binary search, interpolation search, etc)
• cannot generate an off-line index or scan the whole file at start
• changes must be placed in the public domain
• you can start with the existing non-working implementation of seek (see below) or start from scratch
• you'll need to learn about both the ogg specification and the vorbis specification to do this (see the link below for some insight why)
• I (@nothings) am available to provide guidance about what the existing code is doing (aka write better comments)

Current status in the code:

• there is a 2007 implementation of seeking in the code which doesn't work. I no longer remember the details of how it doesn't work. I wrote this document about the frustrations of trying to do a performance-optimal implementation: http://nothings.org/stb_vorbis/ogg_seek.txt but at this point I will accept some suboptimality.
• the "pushdata" API supports an approximate seeking; this is satisfactory for the pushdata API but not for the normal ("pulldata") API. you can just ignore the pushdata case

[Afinostux]

I'd like to give it a shot! On my way to work right now, but I can start reading your code+notes on the train

[MadDavid]

Hello, I have solved this problem as well as it can be solved without an extensive rewrite of vorbis synthesis. Specifically, I'm seeking to the packet that contains the sample, with the first packet decoded returning 0 samples and the 2nd packet decoded returning the desired sample. If this solution is adequate, I would like to integrate my solution with stb_vorbis, and claim the bounty. I will need instructions on that, since this is my first time on GitHub.

[MadDavid]

Also, I suppose I should be a bit clearer. When I say, "the 2nd packet decoded returning the desired sample," I know the offset of the sample inside the packet and could return the number of samples to discard in order to start reading the decoded material at the desired PCM sample. Also, at most 1023 samples will be read and discarded, and on average, approximately 288 PCM samples (~0.006 seconds on the most common frequencies) will be discarded.

[nothings]

I didn't want two people working on this at the same time since only one could claim the bounty, which is why I took down the offer after the first person declared their intent. That person has been working on it steadily since I made the offer. He's not done, but he's still done a bunch of work with the expectation of getting paid for it.

What can I do that's fair?

[eduardo-costa]

Close the bounty.

Stabilish some criteria and choose between the 2 solutions.

If the 2 complement each other share the prize 50-50 and unite them.

2015-05-22 18:50 GMT-03:00 Sean Barrett notifications@github.com:

I didn't want two people working on this at the same time since only one
could claim the bounty, which is why I took down the offer after the first
person declared their intent. That person has been working on it steadily
since I made the offer. He's not done, but he's still done a bunch of work
with the expectation of getting paid for it.

What can I do that's fair?

—
Reply to this email directly or view it on GitHub
#117 (comment).

[image: Imagem inline 1]

[MadDavid]

Understood.

I solved it for my own purposes. But if he gives up, drop me a line.

Madison

On Fri, May 22, 2015 at 4:15 PM, Eduardo Dias da Costa <
notifications@github.com> wrote:

Close the bounty.

Stabilish some criteria and choose between the 2 solutions.

If the 2 complement each other share the prize 50-50 and unite them.

2015-05-22 18:50 GMT-03:00 Sean Barrett notifications@github.com:

I didn't want two people working on this at the same time since only one
could claim the bounty, which is why I took down the offer after the
first
person declared their intent. That person has been working on it steadily
since I made the offer. He's not done, but he's still done a bunch of
work
with the expectation of getting paid for it.

What can I do that's fair?

—
Reply to this email directly or view it on GitHub
#117 (comment).

[image: Imagem inline 1]

—
Reply to this email directly or view it on GitHub
#117 (comment).

[MadDavid]

Or, if he wants info on how to identify the correct packet to start
decoding from (and has already done the other work of integration with
stb_vorbis) and would be willing to share a portion of the bounty (we can
discuss cut.) He could drop me a line and we could work together to finish
it.

On Fri, May 22, 2015 at 5:31 PM, Madison Link madisondavidlink@gmail.com
wrote:

Understood.

I solved it for my own purposes. But if he gives up, drop me a line.

Madison

On Fri, May 22, 2015 at 4:15 PM, Eduardo Dias da Costa <
notifications@github.com> wrote:

Close the bounty.

Stabilish some criteria and choose between the 2 solutions.

If the 2 complement each other share the prize 50-50 and unite them.

2015-05-22 18:50 GMT-03:00 Sean Barrett notifications@github.com:

I didn't want two people working on this at the same time since only one
could claim the bounty, which is why I took down the offer after the
first
person declared their intent. That person has been working on it
steadily
since I made the offer. He's not done, but he's still done a bunch of
work
with the expectation of getting paid for it.

What can I do that's fair?

—
Reply to this email directly or view it on GitHub
#117 (comment).

[image: Imagem inline 1]

—
Reply to this email directly or view it on GitHub
#117 (comment).

[Afinostux]

Currently out of town for family emergency reasons, I'd be happy to discuss it when I get back. Barely any internet access out here

[Afinostux]

Ok, how do I drop you a line? I can't find any sort of private message thing on here

[MadDavid]

madisondavidlink@gmail.com. Also, these messages are coming to my
email, so they're just fine.

------ Original Message ------
From: "Afinostux" notifications@github.com
To: "nothings/stb" stb@noreply.github.com
Cc: "MadDavid" madisondavidlink@gmail.com
Sent: 5/26/2015 6:46:15 PM
Subject: Re: [stb] support for seeking in stb_vorbis.c (bounty) (#117)

Ok, how do I drop you a line? I can't find any sort of private message
thing on here

—
Reply to this email directly or view it on GitHub.

[MadDavid]

Afinostux posted me saying he has had technical difficulties and lost his current work. So I'm proposing we work together to get my stuff compatible with stb vorbis and split the bounty. If no one has any objections, I'll send him a starter PCM seek function tonight and get advice on flushing it out with stb vorbis.

[MadDavid]

Terribly sorry for the delay. Afinostux has not replied to my requests for help on the integration, so I'm just going to have to work it out by myself. I'll start work on it tonight.

[nothings]

I suggest you not work on it any further, at least not with any expectation of the bounty. Currently Afinostux has claim to it if he gets the work done in a reasonable amount of time, and he has been making steady progress.

[MadDavid]

Have you been in touch with afinostux recently? Because on May 27th, he
wrote to me and said
"The laptop I've been working on gave up the ghost, and my working
copy of stb went down with it. Seems like the best
thing to do at this point is to use your solution. I can help you
debug it, if you haven't already done that."

On May 28th, I put together what I had (which was dependent on libvorbis
and my own page-seeking functions) and asked him for advice on how to
use stb_vorbis to seek to pages, get packets, get packet sizes, etc.
etc.

I haven't heard from him since, even though I wrote to him on the 5th
and asked him to let me know if he was going to actually complete the
project.

If you know from communicating with him that he's been working on it
this past week, ok, I'll hold off. But if the backers for this bounty
want results quickly, someone needs to be finishing it.

------ Original Message ------
From: "Sean Barrett" notifications@github.com
To: "nothings/stb" stb@noreply.github.com
Cc: "MadDavid" madisondavidlink@gmail.com
Sent: 6/8/2015 1:29:09 PM
Subject: Re: [stb] support for seeking in stb_vorbis.c (bounty) (#117)

I suggest you not work on it any further, at least not with any
expectation of the bounty. Currently Afinostux has claim to it if he
gets the work done in a reasonable amount of time, and he has been
making steady progress.

—
Reply to this email directly or view it on GitHub.

[nothings]

I have heard from him by email several times since May 27th. The last time was the 4th, when he still was making progress.

[MadDavid]

Again, what's going on with this?

It's been two months since Afinostux started work on this, and 22 days
since Sean said he was "still making progress."

Since the post is still "Open," I assume that the problem has not been
solved.

As an interested party (someone who expects to be receiving a cut of the
bounty) I would like this to be done with. I would certainly like to be
kept in the loop.

Afinostux, are you stuck anywhere in the problem, or do you simply not
have the time to work on it? I would be happy to collaborate or take over
from wherever you are. If I don't hear back from you, I'm going to have to
assume this whole thing is dead, and act accordingly.

On Mon, Jun 8, 2015 at 10:15 PM, Sean Barrett notifications@github.com
wrote:

I have heard from him by email several times since May 27th. The last time
was the 4th, when he still was making progress.

—
Reply to this email directly or view it on GitHub
#117 (comment).

[nothings]

On Jun 19 @Afinostux informed me he was sick, and I told him he could have two weeks to get going on it again. So I want to see where he is this weekend.

"As an interested party (someone who expects to be receiving a cut of the bounty)"

You do expect to receive a cut of it? I was under a different impression. For example, 24 days ago I said "I suggest you not work on it any further, at least not with any expectation of the bounty", and you didn't say anything then to contradict that impression.

[nothings]

Also, what does "act accordingly" in "If [...] I'm going to have to assume this whole thing is dead, and act accordingly" mean?

[MadDavid]

Re: I expect to receive a cut:
When you asked Eduardo what was fair, his options were: Go with the
working solution if one exists immediately, or have me and Afinostux
collaborate and split the bounty if a solution wasn't working immediately.

Afinostux emailed me privately, and said that he had lost ALL work due to a
computer crash.

I figured that he at least had developed a working knowledge of stb_vorbis
and how its existing pagination and packetization functions worked, so I
showed him my code, with function calls that would need to be implemented
in stb_vorbis. Once the function calls are implemented, the code I sent
would start decoding at the desired pcm in the maximally efficient manner
with no audio artifacts. I asked for him to explain to me how to use
stb_vorbis to fill out those function calls, and offered him 1/2 the bounty
in return for his expertise. I get no answer back, and next thing I know,
he's back to work on the problem. I can only assume he's using my code,
because my code is the only way to solve the problem. If he knew how to do
it before, he really should have said. So yes, I and my company expect to
be compensated for our part in this collaboration.

Re: "what does 'act accordingly' mean?
You keep using the word "bounty." A bounty is given to the first person
who shows up with the product. If the payment terms are not like that,
then you really shouldn't be using that word. If I show up Monday with the
complete integration, I should be paid, both per the word "bounty" and per
Eduardo's instructions. After all, while I offered to collaborate with
Afinostux and showed him my work, I owe Afinostux nothing, because he
supplied no help whatsoever to me. Working a lot and seeing someone else
get the money is just a risk of working on a bounty.
And ultimately, I have a working solution (just one that does not use
stb_vorbis) right now. The only reason I've been sitting on it is that I
was under the impression that Afinostux and I are working together on this
problem, with a guaranteed source of payoff. However, if the whole thing
is going to stretch on, I can put my own solution up and start making noise
on every channel interested in Vorbis. You should consider the possibility
that any backers for this bounty want a working solution for efficient
seeking in vorbis, and will take the first one that comes along.
So, flat out, is this a bounty or not?
And as a straight question to Afinostux, do you intend to compensate me for
the work I did and the code I sent you, or not? If so, why not just
explain how to use stb_vorbis's functions to find the correct pages and get
the correct packets and let me work? Quite frankly, if Afinostux had
collaborated with me a month and a half ago, this would have been done by
the first week in June, and we would have the money in our pockets by now.

On Thu, Jul 2, 2015 at 6:01 AM, Sean Barrett notifications@github.com
wrote:

Also, what does "act accordingly" in "I'm going to have to assume this
whole thing is dead, and act accordingly" mean?

—
Reply to this email directly or view it on GitHub
#117 (comment).

[nothings]

Ok, there's a lot to unpack in this response, and a bunch of things don't exactly match up with the stuff already posted in this thread, but that may just reflect some misunderstandings/miscommunication.

*1. "bounty"

When I originally announced this, I called it a bounty, and I thought of it as a traditional bounty. But I immediately realized it could lead to people doing work redundantly, which means it could lead to people doing unpaid work, which I despise, so I clarified it. You can see this in the first sentence on this page ("Someone has declared their intent") and in the fourth paragraph ("Please let me know if you are working on it ... as only one implementation will be paid out.")

I guess in your opinion I should have scrubbed the word "bounty" from it. I can still do that, I guess.

*2. Eduardo

I didn't ask Eduardo what was fair. I asked the interested community (everyone reading the thread) for opinions, and Eduardo is the only one who voiced an opinion, but that didn't make his opinion correct or the winner.

To me, it's implicit in the "please let me know if you're working on it" instruction that only the first intent would be paid (assuming it was successfully completed). If the first successful implementation regardless of intent was paid out, like a traditional bounty, then registering the intents wouldn't accomplish anything at all because someone could still just jump in and claim the bounty. So the fact that I'm asking for intents explicitly implies it's not a bounty in the sense you're talking about.

My assumption was that you had missed the intent instructions entirely, so I wanted to see if there was something fair I could do, but in my opinion the only fair thing was to stick by the original plan ("first intent wins") as long as @Afinostux came through with it.

I didn't explain this explicitly because your replies seemed to accept that idea already, as discussed in the next bullet point.

*3. Your expectation of payment.

I said: "I didn't want two people working on this at the same time since only one could claim the bounty, which is why I took down the offer after the first person declared their intent."

You said: "Understood. I solved it for my own purposes. But if he gives up, drop me a line."

And then: "Or, if he wants info on how to identify the correct packet to start decoding from (and has already done the other work of integration with stb_vorbis) and would be willing to share a portion of the bounty (we can discuss cut.)"

My assumption at this point in time was that you had accepted that the bounty was going to the first intent, and I considered that issue closed.

At that point, you two had some communication offline (between May 22 and May 28).

The impression I came away from afinostux's email after that (IIRC, I'd have to check my email to be sure) was that he was of the opinion that your solution didn't meet the constraints I'd put on it (specifically, I forbade solutions that scanned the entire file first, which--again, IIRC--he said you said you were doing). If source code was shown then, it is the first I've heard of it. (Maybe you were trying to say that with "I put together what I had", but it wasn't quite clear.)

Then we had this exchange:

You said: "I'm proposing we work together to get my stuff compatible with stb vorbis and split the bounty. If no one has any objections,"

You said: "I'm just going to have to work it out by myself."

I said: "I suggest you not work on it any further, at least not with any expectation of the bounty."

These were all posted on the same day; my reply was the first chance I'd had to reply to your "objections" request. Yes, I thought it was a bad idea for you to unilaterally decide to work on it, given the issues with paying out the bounty we'd already discussed.

So I said "don't expect the bounty", you replied asking for clarification if I'd heard from him, I explained that I had, and you didn't reply to that (for three weeks), so I assumed you'd accept the "don't expect the bounty" reply.

*4. Your code

Certainly if @Afinostux has used some of your code it would only be fair that you should share in the bounty. Conversely, does that mean you would be ok with not getting any of the bounty as long as he hasn't used your code?

*5. It could have been done ages ago

I would certainly prefer a solution that was done a month ago and checked-in and resolved and the money paid out (assuming it met the no-scanning-whole-file-constraint and others), but because I chose to go with first intent to try to prevent anybody from working for no money, which I consider more important ethically, that's not how it shakes out. I don't like it, the people who offered to contribute to the bounty don't like it, you don't like it, but ethical prioritiest are ethical priorities.

*6. You releasing your solution independently

I have no problem with this and don't care what you do on your own time, all I care about is what lives in the nothings/stb repository. (FWIW, you mention libvorbis, but libvorbis already has sample-accurate streaming, so I don't really know what you're doing, but again, it doesn't matter to me. If your solution works for you, great!)

From your use of "act accordingly" and "start making noise" I think you're trying to make threats or something? Hard to tell tone of voice on the Internet, though. But, to be clear, if you have a non-stb_vorbis playback solution you want to share with the Internet, you can just go do that. It has nothing to do with the stb situation. (And, if it worries you, as long as you use some open source license other than public domain, we can't "steal" your solution for stb_vorbis anyway.)

*7. "If so, why not just explain how to use stb_vorbis's functions to find the correct pages and get the correct packets and let me work?"

I don't even know what that is asking since that is like 90% of the problem that has to be solved in the first place.

*8. This weekend

As I said before, I gave Afinostux until this weekend to show progress on it. I will update the status of this issue when I find out where he's at. If he backs out, and you still want to seek the bounty, you are welcome to, regardless of whatever noise you make elsewhere. (The one thing that would be a problem would be if you release a fork of stb_vorbis--something you absolutely have every legal right to do but which I would prefer people not to do, for obvious reasons.)

*9. In conclusion

At this point I've spent more than an hour drafting this reply trying to clarify these issues. This is of course a terrible use of my stb-development time. I'm putting in that much time because I'm trying to be as transparent and as fair as I can be, and I'm sorry if it doesn't feel that way to you, @MadDavid, because I'm getting no value out of this other than being transparent and fair (or e.g. the value of being perceived as being transparent and fair); I mean, it's not like I'm saving money somehow, as I expect to pay out the bounty eventually. If your preferred response to this is go tell people about how I'm being non-transparent or non-fair, well, I guess you can do that--I'm not sure what else I can do (while still being fair; as I said, I share your frustration).

[MadDavid]

Your comments on point 1 are fair enough, except that I did not say
"I'll help him for free," I said, "we could work together to finish it.
I also said, on May 28th, "I'm proposing we work together ... and split
the bounty." I understand your objections to unpaid work, and agree
with you scrubbing the word 'bounty', but this means you should
understand my objections to my own contributions going unpaid.

Re: "The impression I came away from afinostux's email after that
(IIRC, I'd have to check my email to be sure) was that he was of the
opinion that your solution didn't meet the constraints I'd put on it
(specifically, I forbade solutions that scanned the entire file first,
which--again, IIRC--he said you said you were doing). If source code was
shown then, it is the first I've heard of it. (Maybe you were trying to
say that with "I put together what I had", but it wasn't quite clear.)"

My own code pre-scans the file once when it is opened. The version I
sent to Afinostux had a place for a function call that merely needed to
locate the page prior to the packet with a known granule position, and
other functions to read the packets without decoding, from there until
the nearest point before the pcm sample at which you can start decoding.
Quite frankly, for heavy-duty seeking I think that performing a binary
file seek is an awkward and time-consuming solution, but my code
supported using it to find the needed page and packets.

Re: "I don't even know what that is asking since that is like 90% of the
problem that has to be solved in the first place."
Maybe, but that's news to me, since the ogg people seemed to think that
a binary file search would be the standard method of seeking a
specific page, and when I looked for solutions on-line, everyone was
asking how to avoid decoding from the previous granule position. No one
was asking how to bisect the file to find the correct page. So 90% of
the code is doing something everyone knows how to do, it's still not 90%
of the problem.

[nothings]

Maybe, but that's news to me, since the ogg people seemed to think that a binary file search would be the standard method of seeking a specific page

...and I have a long rant (written in 2007) explaining why that is a pain in the ass, why the ogg people did a terrible job of making this straightforward to do, linked in the original post up at the top. And moreover this is why I gave up on implementing this myself. The part you've described solving I can indeed trivially solve myself, having written the original code that decoded it at all. Starting with an arbitrary packet and suppressing some samples from the next one is not the hard part of this feature.

[7890]

Hi,
i came here while seeking for a fast way to seek in ogg files.
This discussion is interesting however efforts would be put better to solve the problem in a way everyone can finaly seek nicely.
MadDavid, if you have a working solution: what would be an acceptable bounty to work that into libsndfile?
Sorry for the interruption folks :)

[MadDavid]

Sorry for the late reply. I didn't see this until late Saturday.
Perhaps we should move this discussion to the appropriate page for libsndfile?
You can also contact me directly at http://www.ducksnm.com/support.php. That will get to me faster than my private email. And while you're there, you might look at the WinDOgg page. (WinDOgg is our .dll solution for getting frames of sound from an Ogg file in Windows OS.)
I'll need to look at the fork of libsndfile you want integration with, so that I can see what's involved (It looks like there are a couple of forks.), also I'll need to know if you have any particular demands on the integration. I look forward to hearing from you.

[nothings]

Somebody else sent me a working implementation of seeking.