Rewrite Permalinks for Custom Post type and Custom Taxonomy combination

I have a custom post type called Movies, which shows a listing of movies and info about each one. I also have a custom taxonomy called release_year which is just a 4 digit year. All movies post types have a release_year.

I have my rewrite rules working so that all movies follow: mysite.com/movies/movie-name.

Likewise, I have the rewrite rules for the taxonomy showing as:
mysite.com/movies/release_year/2013

But what I want to happen, is that all movies would always have the rewrite of: mysite.com/movies/year/2013/movie-name (where “year” is constant” and “2013” pulls the taxonomy year on the movies post).

Can anyone give me some ideas or tips on how I might write function or rewrite rule to accomplish this? The Rewrite API still confuses me, as I’m still learning WordPress coding.