No need to re-encode the video. Just split the video at a keyframe and inject an ad at that point, no re-encoding required. Most video files have keyframes every few seconds or so. The proper term is I-frames, though they're commonly known as keyframes as well.