mp4? That's not a video compression format. It's a stream container format. mp4 files might contain RealVideo (ugh) or MPEG1... or pretty much anything really.

mp4? That's not a video compression format. It's a stream container format. mp4 files might contain RealVideo (ugh) or MPEG1... or pretty much anything really. Perhaps you meant h.264 or MPEG-4 (which should not be confused with mp4 container format!). You can decode GIFs with a few hundred lines of code. Decoding different mp4 cases requires several orders of magnitude more code. One big advantage of GIFs is simplicity. So perhaps you could come up with something that could be decoded with at most one or two orders of magnitude more code?