This paper presents and analyzes a new approach to data hiding that embeds in both the intra- and inter-frames from the H.264/AVC video codec. Most of the current video data hiding algorithms take into account only the intra-frames for message embedding. This may be attributed to the perception that inter-frames are highly compressed due to the motion compensation, and any embedding message inside these may adversely affect the compression efficiency significantly. Payload of the inter-frames is also thought to be less, compared with the intra-frames, because of the lesser residual data. We analyze data hiding in both intra- and inter-frames over a wide range of QP values and observe that the payload of the inter is comparable with that of the intra-frames. Message embedding, in only those non-zero quantized transform coefficients (QTCs) which are above a specific threshold, enables us to detect and extract the message on the decoding side. There is no significant effect on the overall bitrate and PSNR of the video bitstream because instead of embedding message in the compressed bitstream, we have embedded it during the encoding process by taking into account the reconstruction loop. For the non-zero QTCs, in the case of intra-frames, we benefit from the spatial masking, while in the case of inter-frames, we exploit the motion and texture masking. We can notice that the data hiding is done during the compression process and the proposed scheme takes into account the reconstruction loop. The proposed scheme does not target robustness and the obtained payload is higher, with a better trade-off in terms of quality and bitrate, as compared with previous works.