[FFmpeg-devel] [PATCH] avformat/assenc: honor ReadOrder

[Michael Niedermayer]

On Sat, Sep 13, 2014 at 09:06:56PM +0200, Clément Bœsch wrote:
> ---
>  libavformat/assenc.c | 89 +++++++++++++++++++++++++++++++++++++++++++++++++---
>  1 file changed, 85 insertions(+), 4 deletions(-)
> 
> diff --git a/libavformat/assenc.c b/libavformat/assenc.c
> index 9fb9f23..acc21b9 100644
> --- a/libavformat/assenc.c
> +++ b/libavformat/assenc.c
> @@ -19,12 +19,22 @@
>   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
>   */
>  
> +#include "libavutil/avstring.h"
>  #include "avformat.h"
>  #include "internal.h"
>  
> +typedef struct DialogueLine {
> +    int readorder;
> +    char *line;
> +    struct DialogueLine *prev, *next;
> +} DialogueLine;
> +
>  typedef struct ASSContext{
>      unsigned int extra_index;
>      int write_ts; // 0: ssa (timing in payload), 1: ass (matroska like)
> +    int expected_readorder;
> +    DialogueLine *dialogue_cache;
> +    int cache_size;
>  }ASSContext;
>  
>  static int write_header(AVFormatContext *s)
> @@ -60,19 +70,82 @@ static int write_header(AVFormatContext *s)
>      return 0;
>  }
>  
> +static void purge_dialogues(AVFormatContext *s, int force)
> +{
> +    int n = 0;
> +    ASSContext *ass = s->priv_data;
> +    DialogueLine *dialogue = ass->dialogue_cache;
> +
> +    while (dialogue && (dialogue->readorder == ass->expected_readorder || force)) {
> +        DialogueLine *next = dialogue->next;
> +        if (dialogue->readorder != ass->expected_readorder) {
> +            av_log(s, AV_LOG_WARNING, "ReadOrder gap found between %d and %d\n",
> +                   ass->expected_readorder, dialogue->readorder);
> +            ass->expected_readorder = dialogue->readorder;
> +        }
> +        avio_printf(s->pb, "Dialogue: %s\r\n", dialogue->line);
> +        av_free(dialogue->line);
> +        av_free(dialogue);
> +        if (next)
> +            next->prev = NULL;
> +        dialogue = ass->dialogue_cache = next;
> +        ass->expected_readorder++;
> +        n++;
> +    }
> +    ass->cache_size -= n;
> +    if (n > 1)
> +        av_log(s, AV_LOG_DEBUG, "wrote %d ASS lines, cached dialogues: %d, waiting for event id %d\n",
> +               n, ass->cache_size, ass->expected_readorder);
> +}
> +
> +static void insert_dialogue(ASSContext *ass, DialogueLine *dialogue)
> +{
> +    DialogueLine *cur, *next, *prev = NULL;
> +
> +    next = ass->dialogue_cache;
> +    for (cur = next; cur; cur = cur->next) {
> +        if (cur->readorder > dialogue->readorder)
> +            break;
> +        prev = cur;
> +        next = cur->next;
> +    }
> +    if (prev) {
> +        prev->next = dialogue;
> +        dialogue->prev = prev;
> +    } else {
> +        dialogue->prev = ass->dialogue_cache;
> +        ass->dialogue_cache = dialogue;
> +    }
> +    if (next) {
> +        next->prev = dialogue;
> +        dialogue->next = next;
> +    }
> +    ass->cache_size++;
> +}

iam not sure what the typical insert vs remove statistics are but
this looks like O(n^2) time to me, which might be a problem if there
are millions of entries

for a mixed insert + remove "lowest" data structure, theres heap
sort with O(n log n) worst case, or various other options


[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Democracy is the form of government in which you can choose your dictator
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <https://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20140913/88fc900f/attachment.asc>